Help with proof of the existance of a graph produced from deleting edges

Question

Prove that every connected graph with an even number of vertices can be transformed into a graph with uniform degree 1 by only deleting edges.

I have tested this with pen-and-paper and it seems to be true. If someone knows a clever proof, and can explain how you derived it, it would be awesome.

Answer 1

This is not true. For example pick $G$ to be a star graph.

The vertices are $v, v_1,.., v_{2n-1}$ and the edges are $vv_1, vv_2,..., vv_{2n-1}$.

If you erase any edge in this graph, you create a vertex of degree 0.

The smallest example is the following graph $$ \cdot - \cdot - \cdot \\ |\\ \cdot$$

P.S. The way I derived the counterexample is simple: I tried to prove your result: If it is true, it must also hold for trees, and by picking a spanning tree it would be enough to prove it for trees.

For a tree, a good starting point is a leaf, if we start at a leaf, there is only one way to leave it with degree 1, we need to disconect the tree at the adjacent vertex to the leaf. But then there was a problem, namely if you get the above configuration...

Answer 2

It is not true. Let us consider the graph $G=(V,E)$ in which $V=\{0,1,2,3\}$ and $E=\{(0,1), (0,2), (0,3)\}$. The graph $G$ has $4$ vertices and is clearly connected. However, you cannot produce a graph with uniform degree $1$ by only deleting edges.