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 ?
Graph is $2$-edge-connected, when vertices has even degrees
591 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail AtThere are 2 best solutions below
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.
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.