I have to prove that Connected graph is Eulerian Graph if and only if the number of edges in minimal cut is even.

Implication from left to right. Well if $G$ is Eulerian Graph then degree of each vertex must be even. It's oblivious if i try to disconnect graph by removing all edges connected to the vertex with minimal degree. But minimal cut can be done also by dividing graph into 2 connected graphs (each graph with more then one vertex) and i have no idea how to deal with it.

Implication from right to left - completly no idea.

  • $\begingroup$ Does the statement "the number of edges in a minimal cut is even" mean "the number of edges in every minimal cut is even" or does it mean "the number of edges in some minimal cut is even"? I'm guessing it's "every", because there are easy examples of non-Eulerian connected graphs in which some minimal cut has an even number of edges. On the other hand, "every" makes the right-to-left implication trivial, because it implies that each vertex has even degree. $\endgroup$ – bof Jan 9 '14 at 4:12

Right to left: If every minimal cut has an even number of edges, then in particular the degree of each vertex is even. Since the graph is connected, that means it is Eulerian.

Left to right: A minimal cut disconnects $G$ into two components $G_1$ and $G_2$. The degree sum of $G_1$ (which is even by the Handshake Theorem) = the sum of the original degrees in $G$ of the vertices of $G_1$ (which is even because $G$ is Eulerian) minus the number of edges in the minimal cut (which is therefore even, being the difference of two even numbers).


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.