Results 1 to 4 of 4

Math Help - Spanning Subgraph

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by jzellt View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2007
    Posts
    24

    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.
    Last edited by machi4velli; November 21st 2011 at 10:29 PM. Reason: I left out a word
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Spanning Subgraph

    Never mind. I can't read.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 6th 2011, 06:13 PM
  2. spanning set
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 24th 2010, 11:46 AM
  3. how many subgraph...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 08:03 AM
  4. subgraph
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 20th 2008, 01:17 AM
  5. Subgraph Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 8th 2008, 01:33 PM

Search Tags


/mathhelpforum @mathhelpforum