# 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. – Thomas Andrews 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. – Thomas Andrews 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. – Thomas Andrews 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.