So i need help with this: Let T be a tree. And degree of every vertice is an odd number. So i need to prove that there is an odd number of paths in that tree.
So i basically need to prove that there is an even number of vertices.
So probably i could use a method like this: Let $$|V(T)|= x$$ and let x be an odd number, so i want to get into a contradiction. Is that the correct way Any help with this would be appreciated.
The proof is pretty easy:
In any tree $T$ we have $$ |V(T)|= |E(T)|-1$$ where |E(T)| is the number of edges in $T$
Note that $$|E(T)|=\frac{1}{2}\sum_{v\in T} d(v) $$ Then we have two case
1- $ \frac{1}{2}\sum_{v\in T} d(v) $ is odd and thus $ |V(T)|$ is even
2- $ \frac{1}{2}\sum_{v\in T} d(v) $ is even and thus $ |V(T)|$ is also even (Since $d(v)$ is odd $\forall v\in T$) ( in this case it can not be a tree)