ON VERTICES OF DEGREE 6 OF MINIMAL AND CONTRACTION CRITICAL 6-CONNECTED GRAPH

摘要

The goal of the paper is to study vertices of degree 6 of minimal and contraction critical 6-connected graph, i.e., a 6-connected graph that looses 6-connectivity both upon removal and upon contraction of any edge. It is proved that if x and z are adjacent vertices of degree 6, then x and z have at least 4 common neighbors. In addition, a detailed description of the neighborhood of the set {x, z} is given. An infinite series of examples of minimal and contraction critical 6-connected graphs for which the fraction of vertices of degree 6 equals 1117documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ rac{11}{17} $$end{document} is constructed.