3-connected graphs simple question

$\begingroup$

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.

$\endgroup$ 6

1 Answer

$\begingroup$

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.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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