Isomorphic Factorization
A graph H divides a graph G if the edge set of G can
be partitioned into copies of H.
Factoring Complete Graphs into Trivalent Graphs
There are 19 trivalent graphs of order 10. Of these,
14 divide K10. The five that don't are
shown in the figure below.
Factoring Complete Graphs into Spanning Trees
In order for a tree T of order n to divide the complete
graph Kn,
n must be even and the maximum degree of T
can be at most n/2.
The degree sequence of a tree of order n does not
determine whether or not it divides Kn.
There are two trees with degree sequence
3,2,2,1,1,1. They are shown in the figure below. The top tree
does not divide K6 while the bottom one
does.
The table below gives some data from
computational experiments.
| Order |
# Trees |
# Trees of Max Deg n/2 or less |
# Trees that Divide Kn |
| 4 |
2 |
1 |
1 |
| 6 |
6 |
4 |
3 |
| 8 |
23 |
18 |
14 |
| 10 |
106 |
94 |
85 |
| 12 |
551 |
520 |
484+ |
