I have a relatively simple question. I was given this exercise

A graph $G$ is called $2$–connected if for every pair of vertices $x$ and $y$ there are at least $3$ internally disjoint $xy$–paths in G. Show that every $3$–connected graph has an even cycle. (Hint: Use Menger’s theorem)

But if a graph is $3$-connected there is at least 3 internally disjoint paths between any $x$ and $y$. So $2$ will have to same parity. Take the union of these and the cycle is even.

Is this correct? I have not used the hint and it seems to be way too simple.

  • $\begingroup$ I cannot see anything wrong in your proof. $\endgroup$ – Peter Nov 19 '14 at 19:37
  • $\begingroup$ Is " A graph G is called $2$-connected " a typo ? I think it should be "$3$-connected". $\endgroup$ – Peter Nov 19 '14 at 20:06
  • $\begingroup$ I copied it straight from the problem, so I dont think it's a typo. This is the only definition of $k$-connected I have seen. $\endgroup$ – George Clinton Nov 19 '14 at 20:08
  • $\begingroup$ But a $2$-connected graph need not have $3$ internally disjoint $xy$-paths for every pair $x,y$. $\endgroup$ – Peter Nov 19 '14 at 20:09
  • $\begingroup$ Okay. But this doesn't change the basis for my proof since it will still have 3 $xy$ internally disjoint paths. $\endgroup$ – George Clinton Nov 19 '14 at 20:10

Yes, your proof is correct. Suppose the graph is 3-connected. Pick any two distinct vertices $x$ and $y$. By Menger's theorem there exist three (internally vertex-) disjoint $xy$-paths. By the pigeonhole principle, two of the three paths must have the same parity. The union of these two paths is an even cycle.


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.