A tree is a connected graph with no cycles. How many nonisomorphic trees with \(5\) vertices exist?
(A) \(1\) (B) \(2\) (C) \(3\) (D) \(4\) (E) \(5\)
Answer:
(C)
Answer Key:
A tree with \(5\) vertices have \(5-1=4\) edges.
To see this, starting with a node, attach edge + node one at a time to construct a tree.
The degree of a node is the number of edges attached ("incident") to the node.
Every edge is incident to two nodes.
So, the sum of degrees have to be \(4\times2=8\).
Isomorphic trees have the same degree sequence.
A degree sequence lists the degree of nodes in an descending order.
In other words, if \((d_1,d_2,d_3,d_4,d_5)\) is a degree sequence, \(d_i\ge d_j\) when \(i\lt j\) and \(d_1+d_2+d_3+d_4+d_5=8\).
All possible degree sequences are \((4,1,1,1,1)\), \((3,2,1,1,1)\), and \((2,2,2,1,1)\).
Corresponding trees are shown below.
No comments:
Post a Comment