Prove that if G is a tree in which all vertices have odd degree then G has odd size.

Question

Prove that if G is a tree in which all vertices have odd degree then G has odd size. Good night, do not know how to approach this "prove". Can you give me tips to solve it?. Please.

Answer 1

Hint: Consider the sum of the degrees of all of the vertices. Every edge contributes to this sum twice, so the sum is even. What happens if you have an odd number of vertices, each with an odd degree?

Answer 2

Remember the "first theorem of graph theory:" $$\sum_{v \in V(G)} \deg v =2|E(G)|,$$

where $V(G)$ denotes the vertex set and $E(G)$ the edge set.

If $\deg v$ is odd for each vertex, what does the above say about the parity (even or odd) of $|V(G)|$? Once you've figured this out, you still need to translate this into a statement about the size of the graph, which is $|E(G)|$. This is where you use that $G$ is a tree: what do you know relating the number of elements of the vertex set to the number of elements of the edge set for a tree?