For each tree with even amount of vertices, there is only one spanning graph, where all vertices have odd degree.

177 Views Asked by At

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:

  1. We'll assume there are 2 different spanning graphs $G_1,G_2$ of $T$ that satisfy the constraint above, and show a contradiction.
  2. Since both different there exists a vertex $v$, whose degree is different in $G_1,G_2$.
  3. 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.
  4. 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.