Thread: 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?

Originally Posted by BSC hiBi

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 . (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 ).

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 ? If 3n is congruent to 2 (mod 4) then n itself will be congruent to 2 (mod 4). So why bother with the 3?