I have this problem which I solved partially:
Let $T$ be a tree (doesn't necessarily mean a binary tree), we'll assume $|V_T|=k$, where $k$ is even. Prove that $T$ has a spanning graph where: $\forall {v\in V_T, deg(v)}$ is odd. Additionally prove this is the only graph that satisfies it.
Edit: a spanning subgraph of a graph $G=<V,E>$ is defined to be: $G'=<V,E'>$ where $E' \subset E$
I have completed the first part of this question, and understood it, but could't complete the second part.
I tried the next approach:
- We'll assume there are 2 different spanning graphs $G_1,G_2$ of $T$ that satisfy the constraint above, and show a contradiction.
- Since both different there exists a vertex $v$, whose degree is different in $G_1,G_2$.
- Since both $G_1,G_2$ spanning graphs of the same tree there's only one path from each vertex to $v$. Therefore, in one of the graphs $v$'s degree is smaller than the other's.
- Without loss of generality assume: $deg_1(v)<deg_2(v)$. Consider the next cases:
a. $deg_2(v)=1 \rightarrow 0\leq deg_1(v)<deg_2(v) \rightarrow deg_1(v)=0$, which is even, which contradicts the assumption that all the vertices in $G_1$ have an odd degree.
b. $deg_2(v)-deg_1(v)=$ odd number $\rightarrow$ one of $deg_2(v),deg_1(v)$ is even, which contradicts the assumption on $G_1,G_2$.
c. $deg_2(v)-deg_1(v)=$ even number $\rightarrow$ each neighbour that was connected to $v$ and now isn't has an even degree...(It's not done here, I need to show that each sub graph that was created by detaching edges from $v$ has a vertex with even degree).
And that's pretty much where I'm stuck at the moment. I can't tell whether this proof compiles/works or leads me to the desired outcome. I would appreciate any proof with an explanation.