Results 1 to 2 of 2

Math Help - Tree with MOD proof

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    16

    Tree with MOD proof

    Let T be a tree with n vertices. Suppose n only has vertices with degree 1 and 5. Show that 3n = 2 (mod 4).

    Where the equal sign is the mod sign (3 lines instead of 2.)

    I think this will require induction as the vertices will always be 2, 6, 10, 14, 18, etc. Any help?
    Last edited by BSC hiBi; April 11th 2009 at 01:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by BSC hiBi View Post
    Let T be a tree with n vertices. Suppose n only has vertices with degree 1 and 5. Show that 3n = 2 (mod 4).

    Where the equal sign is the mod sign (3 lines instead of 2.)

    I think this will require induction as the vertices will always be 2, 6, 10, 14, 18, etc. Any help?
    Here's an intuitive argument based on a sort of induction. The idea is to build up the graph starting from a vertex of degree 1. Such a vertex must exist because a tree has branches that end in twigs.

    That vertex is connected to one other vertex. These two vertices together form a sub-tree with 2 vertices. Note that 3\times2\equiv2\!\!\!\pmod4. (That is the base case for the "induction".)

    If that second vertex is connected to another vertex, it does not have degree 1, so it must have degree 5. Therefore it is connected to 4 new vertices. Add those vertices to the tree that we are building up. So we now have a sub-tree with 6 vertices (and 3\times6\equiv2\!\!\!\pmod4).

    Now continue building up the graph in that way. At each stage we have to add 4 new vertices, so three times the total number of vertices in the sub-graph will always be congruent to 2 (mod 4).

    Question: Why does the problem ask us to show that \mathbf{3}n\equiv2\!\!\!\pmod4? If 3n is congruent to 2 (mod 4) then n itself will be congruent to 2 (mod 4). So why bother with the 3?
    Last edited by Opalg; April 13th 2009 at 12:01 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. binary tree math proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 14th 2012, 03:24 AM
  2. Proof Tree induction - proving conjunction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: October 16th 2011, 11:58 AM
  3. tree
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 25th 2011, 06:56 AM
  4. Tree Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 22nd 2010, 07:36 PM
  5. Growing tree
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 25th 2008, 10:03 PM

Search Tags


/mathhelpforum @mathhelpforum