6.2. Decompositions

A decomposition of a graph G is a collection of nonempty subgraphs  such that  for some nonempty subset , where is a partition of .

Consequence: No subgraph  in a decomposition of G contains isolated vertex.

If  is a decomposition of G, then we write

,

as we do with factorization., and say G is decomposed into sub-graphs , where then .

What is the connection between factorization and decomposition?

If , is a decomposition of a graph G of order n and we define  , then

,

is a factorization of G.

Every factorization of a nonempty graph also gives rise to a decomposition of G:

Suppose that  is a factorization of a nonempty graph G, so written that   are nonempty .

Let . Then  is a decomposition of G.

If  is a decomposition of a graph G such that  for some graph H for each i, then G is said to be H-decomposable. In that case we also write  and say that H divides G, or G is a multiple of H.

If G is H-decomposable, then . Although  this condition is necessary, it is easy to see that it is not sufficient. ( divides the size 12 of G, but G is not -decomposable.)

The basic problem in this context: given a graph G and a subgraph H of G whose size divides that of G whether, the graph G is H-decomposable. Evidences:

  • Every graph is -decomposable
  • Every component of a -decomposable graph has even size.

Theorem 6.5. A nontrivial connected graph G is -decomposable iff G has even size.

Proof.

The necessary part of the statement is obvious.

For the converse, assume that G has even size.

Suppose, first, that G is eulerian, where the edges of G are encountered in the order .

Then each of the sets  induce a copy of . So G is -decomposable.

Otherwise, G has 2k odd vertices for some .

By Theorem 6.3,  can be partitioned into subsets , where for each  is an open trail  of even length connecting odd vertices of G.

Then, as with the eulerian circuit above, the edges of each trail  can be paired off so that each pair of edges induces a copy of .

Theorem 6.6. A nontrivial graph G is -decomposable iff G has even size  and .

Theorem 6.7. The complete graph Kn is K3-decomposable iff n is odd and .

Theorem 6.8. (Wilson, 1975): For every graph H without isolated vertices and having size m, there exists a positive integer N such that

where

then  is H-decomposable.