Help with proof of the existance of a graph produced from deleting edges 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.
 A: 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...
A: 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.
