# Graph formed from a cycle is $3$-connected proof

Definition: Two vertices are connected in a graph when there is a path that begins at one and ends at the other.

Definition: Two vertices in a graph are $$k$$-edge connected when they remain connected in every subgraph obtained by deleting up to $$k - 1$$ edges. A graph is $$k$$-edge connected when it has more than one vertex, and every subgraph obtained by deleting at most $$k - 1$$ edges is connected

Let $$G$$ be a graph formed from $$C_{2n}$$, the cycle of length $$2n$$, by connecting every pair of vertices at maximum distance from each other in $$C_{2n}$$ by an edge in $$G$$

Prove that the graph is not $$4$$-connected.

Prove that the graph is $$3$$-connected.

I got stuck at this question, here I tried to use induction on number of vertices, but the problem is I could not find a way to partition graph $$G$$ formed from $$C_{2(n+1)}$$ to a graph $$G'$$ formed from $$C_{(2n)}$$, so that then induction hypotesis $$P(n)$$ can be used for the proof.

• There are only three edges coming from any vertex, so the first part is easy. Aug 5 '13 at 13:32
• The relationship between $C_{2(n+1)}$ and $C_{2n}$ is not obvious, so I don't think induction will be useful, but I could be wrong. Aug 5 '13 at 13:33
• Is it obvious that $C_{2n}$ is $2$-connected? So to make it disconnected, you'd have to remove two edges? Now, add the "cross-edges" back into the mix, and show that removing any two edges from $C_{2n}$ doesn't make the extended graph disconnected. Aug 5 '13 at 13:36
• @ThomasAndrews This shows $3$-edge connectedness, which is strictly weaker than $3$-connectedness.
– A.S
Aug 5 '13 at 18:39

Hint: think about the number of paths between any tow vertices.

Edit: And after you will figure this out you have Menger's theorem. Which says that a graph $G$ is K connected $\iff$ for every tow vertices there is a K pathes between them.

• It's important to note that for Menger's theorem to be applied, the interiors of the paths must be vertex-disjoint (have no vertices in common).
– A.S
Aug 7 '13 at 9:55

The first part is easy: take any vertex $v$ and delete $3$ of its neighbors.

To prove the second part, exhibit an open-ear decomposition for $G-v$.

Label the vertices $v_1$ through $v_{2n}$, and without loss of generality, delete $v_1$ (symmetry allows us to reduce the problem in this way). A starting cycle for $G-v_1$ is $v_2 C v_n v_{2n} C v_{n+2}$. Call this graph $H$. Add the $H$-path $v_{n+2} v_{n+1} v_n$. Then add the rest of the edges one by one, which are all $H$-paths.

Since $G-v$ is $2$-connected for all $v$, $G$ is $3$-connected.