Graph is $2$-edge-connected, when vertices has even degrees

591 Views Asked by At

Let $G = (V,E)$ be a connected graph with at least $3$ vertices. Assume that $\forall v \in V$ is $\deg(v)$ an even number. How can i prove that than G must be $2$-edge-connected ?

2

There are 2 best solutions below

2
On BEST ANSWER

Suppose there is cut edge $ab$. Then $a$ is in component $A$ and $b$ in component $B$

But then $a$ is the only vertex with odd degree in $A$ which is a contradiction by handshake lemma.

0
On

There is an even stronger (and also more famous) result: when every vertex has even degree, then there is an Euler circuit, that is: a path through the graph that begins and ends in the same vertex and visit every edge exactly once. (In other words: you can draw the graph without lifting your pen of the paper and without drawing the same line twice, moreover ending where you started.)

From the circular nature of this circuit 2-connectedness follows easily. The real question is why this stronger result (due to Euler) is true. You can either look it up on the internet (search for Bridges of Koningsberg) or try and prove it yourself: sometimes proving a stronger result is easier than proving the original claim, and this might be one of these cases.