|
|
Each complete graph with the even number n of vertices can be covered with trees (split into them). A trivial decomposition is into the set of stars Sn till S2. Another possibility is into (n/2 - 1) trees with n vertices.
The proof follows:
Since the complete graph Kn has n(n - 1)/2 edges (arcs) there exists the possibility to split them into n/2 separate sets of the covering trees with (n – 1) edges.
K4 is splited into two linear chains L4. All trees with the even number n of vertices, except L2, can be split into a bistar and a complete graph K(n-2) which had one half of its vertices connected to one central vertex of the bistar and the other half of its vertices connected to the other central vertex of the bistar.
The complete graph K(n-2) can be split into (n/2 - 1) trees T(n-2). To them one edge to both inner vertices of the bistar is attached.
This set together with the bistar is one from the possible decompositions. The (n/2 - 1) edges of the bistar can be exploited for completing of (n/2 – 1) trees T(n-2) to the trees Tn, leaving K2.
The decomsitions are not unique, since there are possible different choices of the ending edges to inner parts of trees.