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.

  • 3
    $\begingroup$ There are only three edges coming from any vertex, so the first part is easy. $\endgroup$ Aug 5 '13 at 13:32
  • $\begingroup$ 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. $\endgroup$ Aug 5 '13 at 13:33
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 5 '13 at 13:36
  • $\begingroup$ @ThomasAndrews This shows $3$-edge connectedness, which is strictly weaker than $3$-connectedness. $\endgroup$
    – 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.

  • $\begingroup$ 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). $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.