Extremal 3-connected graphs (Q1106857)

Theorem 2: Let G be a 3-connected graph with minimum degree at least d and with at least 2d-1 vertices. Then for any 3 distinct vertices x, y, z there is a path from x to z through y and having length at least 2d-2. Furthermore, suppose that G has at least 2d vertices, that no set of exactly d vertices meets every edge and that for every vertex \(v\neq x\), z, G-\(\{\) x,v,z\(\}\) has a component which is not a complete graph \(K_{d-2}\). Then there is a path from x to z through y and having length at least 2d-1. From the proof of this theorem it follows that there are only the next two extremal examples of graphs having more than 2d-1 vertices. Example 1. Let H be any graph on d vertices and let S be an independent set of vertices disjoint from H, \(| S| \geq d-1\). Let G be the graph obtained by adding edges from every vertex of S to every vertex of H. Example 2. Let H be the disjoint union of complete graphs each having d-2 vertices. Let x, z, v be three vertices disjoint from H and let F be any graph with \(V(F)=\{x,v,z\}\). Let G be the graph obtained by joining every vertex of H to every vertex of F.