[Math] Prove that every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex.

discrete mathematicsgraph theory

I need to prove/disprove the following statement —

If every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex.

I am a bit confused about one of the terms:

  1. what does it actually mean by "every minimal" ? I know minimal edge cut is a "cut" that is not maximal (so a minimum edge cut is also a minimal). Therefore there could be multiple number of minimal edge cuts that is not maximal. Am I right?

Above all, how do I prove it? I am thoroughly confused (even don't know where to start).

This fact may be useful: In any connected simple graph, the total number of odd degree vertices are always even (from Handshaking lemma).

Best Answer

A minimal edge cut is not defined as an edge cut that is not maximal. It is defined as an edge cut that does not contain a smaller edge cut. (A minimum edge cut would be an edge cut that has the minimum number of edges among all edge cuts).

Now if you remove all edges incident with a given vertex, you certainly have an edge cut, but it need not be a minimal edge cut. An example is given by the claw $K_{1,3}$: if you remove all edges incident with the center you have an edge cut $S$ of size 3, but this edge cut is not minimal: each edge (as a singleton) is also an edge cut, that is contained in $S$.

Assume the claim is untrue. Then there is a vertex $v$ of odd degree, but nevertheless every minimal edge cut is even. This means that the (odd) edge cut $S_1$ determined by the edges incident to $v$ contains a smaller (even) edge cut $T_1$.

But then $S_2=S_1-T_1$ is also an edge cut (you need to prove this!). Unfortunately it is still odd, so it contains an even smaller (even) edge cut $T_2$. Again $S_3=S_2-T_2$ is an edge cut, and so on.

This process goes on forever, but since we only have a finite number of vertices and since the cuts get strictly smaller at each step, it must finish.

This contradiction proves that the claim must be true.

(The iteration can be avoided by immediately taking a maximal even edge cut in $S_1$, but that does not really lead to a better proof).

Related Question