Proof: We have a graph where all nodes have an even degree, then the graph is 2-edge-connected.

610 Views Asked by At

Assuming we have a connected graph where all nodes have an even degree, then the graph is 2-edge-connected.

The inverse implication of the statement is wrong (I found a counterexample). But for this statement I can't find a counterexample and I think that this statement is true. How can I prove it ?

1

There are 1 best solutions below

6
On

Suppose that you start with an even graph, and deleting an edge leaves two components: one with $k$ vertices, and one with $n-k$. What can you say about the degrees of the vertices in each component?