1. ## Spanning Subgraph

Let T be a tree of even order (even number of vertices). Prove that T has exactly
one spanning subgraph in which each vertex has odd degree.

Thanks for any help...

2. Originally Posted by jzellt
Let T be a tree of even order (even number of vertices). Prove that T has exactly
one spanning subgraph in which each vertex has odd degree.

Thanks for any help...
I'm a tad confused as to how this problem is posed. A tree has precisely one spanning subgraph (itself).

What also confuses me, although less so, is that the result isn't actually true. Take 4 vertices and place them in a line, so you have a tree with 4 vertices and 3 edges. Clearly such a tree does not have a spanning tree where each vertex has odd degree.

So, I'm not entirely sure how to help you. I would point out, however, that if you have an even number of vertices then there exists a tree which spans these vertices, which is simply the tree with one (unique) vertex connected to all the others. Therefore, if there are 2n vertices this vertex will have degree 2n-1, while all the other vertices have degree 1. This may or may not be the result you are looking for...

3. ## Re: Spanning Subgraph

A spanning subgraph is a subgraph of a graph consisting of the same vertex set and a subset of the edge set of the graph, which is not necessarily a tree. A spanning tree is a spanning subgraph that is also a tree.

Anyway, for the question, you can use induction on the number of vertices = 2k. For k = 1, we have 2 vertices, and so there is only one possible tree, which is just two vertices connected by 1 edge -- the graph itself is a spanning subgraph with odd vertices.

Suppose for k >= 1, every tree with 2k vertices has a unique spanning subgraph with all odd vertices.

Now since each leaf has degree 1 in the tree, any such spanning subgraph must include all edges incident to leaves.

Consider a tree with 2(k+1) vertices. Consider a longest possible path in this tree. Suppose 1 endpoint of the path is a vertex v, which would have to be a leaf. Suppose u is the vertex adjacent to u in the path.

Case 1: u has another adjacent leaf, call it w.
T - {v, w} has a unique such spanning subgraph by our assumption (we assumed this for any tree with 2k vertices), so use that spanning subgraph and add edges uv and uw -- the degree of u gains 2, so it stays odd, and v and w only have the 1 incident edge, so their degree will be 1, which is odd, and we have the type of subgraph we need.

Case 2: u has no other adjacent leaf.
Since p is the longest path, this means the degree of u is 2, or else there would be a cycle in the graph. So, we know that T - {u, v} has a unique such spanning subgraph by assumption -- add uv to that subgraph and we have the type of subgraph we need (u + uv + v will be a separate component).

So, by induction, this holds for any number of vertices 2n for a positive integer n.

,

,

,

# odd degree of tree

Click on a term to search for related topics.