Decomposition of a complete graph into maximal matching subgraphs

2011-10-17T21:11:57Z

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?

For example, consider $K_4$ with vertices $V=${1,2,3,4}. It can be decomposed into the union:

$K_4=$ {{1,2},{3,4}} $\cup$ {{1,3},{2,4}} $\cup$ {{1,4},{2,3}}

In this example, none of the 3 subgraphs share an edge. For $n$ odd, I could easily find a general decomposition of $K_n$ into $n$ "independent" maximal matching subgraphs:

$K_n= \bigcup_\sigma$ { {$\sigma(1),\sigma(n-1)$}, {$\sigma(2),\sigma(n-2)$}, ... }

where the union is over all cyclic permutations $\sigma$ of the vertex set $V=${1,2,...,$n$}. For $n$ even, however, I can't find a general solution for this decomposition problem, which would involve the union of $n-1$ subgraphs. I can solve it for particular examples, like $K_4$, $K_6$ and $K_8$, but not for the general $n$ even case.

Answer by Gerry Myerson for Decomposition of a complete graph into maximal matching subgraphs

2011-10-17T21:20:39Z

Let the $2n$ vertices be the $2n-1$ vertices of a regular polygon and its center. Join the center to one of the other vertices by a line segment $S$, then join the remaining $2n-2$ vertices in pairs by line segments perpendicular to $S$. That's one maximal matching subgraph. Now rotate the vertices around the center through $2\pi k/n$, $k=1,2,\dots,$, while keeping the line segments where they are. That will give you the rest of the maximal matching subgraphs which together decompose $K_{2n}$.

Decomposition of a complete graph into maximal matching subgraphs - MathOverflow

Decomposition of a complete graph into maximal matching subgraphs

Answer by Gerry Myerson for Decomposition of a complete graph into maximal matching subgraphs