1
$\begingroup$

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).

$\endgroup$

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ could you please elaborate a bit more on "does not contain a smaller edge cut"? the only way to isolate a single vertex is to have a cut over all the edges connected to it, so why are we saying it as "minimal"? this is the only "cut" that we have and it's "minimum". $\endgroup$
    – ramgorur
    Feb 21, 2015 at 7:41
  • $\begingroup$ ok, lets say we have an edge cut $C$ that contains a smaller edge cut $C'$, and suppose $C'$ does not contain any smaller edge cut anymore. So, $C'$ is minimal, then why we are not calling $C'$ as "minimum" (instead of minimal)? $\endgroup$
    – ramgorur
    Feb 21, 2015 at 7:49
  • $\begingroup$ Initial answer was too short. Added some explanation about minimum and minimal and an almost complete proof. $\endgroup$ Feb 21, 2015 at 9:54
  • $\begingroup$ now it explains a lot, thanks. $\endgroup$
    – ramgorur
    Feb 21, 2015 at 11:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .