A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x , or there is a specified structure called a K 4 − ‐configuration with center x . As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2 n /5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009