# 3-connected graphs simple question

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.

• I cannot see anything wrong in your proof. – Peter Nov 19 '14 at 19:37
• Is " A graph G is called $2$-connected " a typo ? I think it should be "$3$-connected". – Peter Nov 19 '14 at 20:06
• 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. – George Clinton Nov 19 '14 at 20:08
• But a $2$-connected graph need not have $3$ internally disjoint $xy$-paths for every pair $x,y$. – Peter Nov 19 '14 at 20:09
• Okay. But this doesn't change the basis for my proof since it will still have 3 $xy$ internally disjoint paths. – 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.