5
$\begingroup$

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.

$\endgroup$

1 Answer 1

11
$\begingroup$

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}$.

$\endgroup$
6
  • 2
    $\begingroup$ Agreed, and note that this is called a 1-factorization or perfect factorization of $K_{2n}$. Searching on those phrases will uncover a large amount of theory including other constructions. $\endgroup$ Oct 17, 2011 at 21:24
  • $\begingroup$ That's it! The solution is so simple! I feel ashamed. Thank you very much, Gerry! $\endgroup$
    – FreeQuark
    Oct 17, 2011 at 21:33
  • $\begingroup$ Thank you for the input, Brendan. I am totally ignorant about graph theory, I only took a glance at it yesterday and today to try to understand this particular combinatorial problem. I will try to learn more into 1-factorization and perfect factorization, as it might be useful in my computer program I'm developing. $\endgroup$
    – FreeQuark
    Oct 17, 2011 at 21:38
  • $\begingroup$ Is there a similar decomposition involving a "n-gonal prism" that produces n isomorphic factors? Gerhard "Ask Me About System Design" Paseman, 2011.10.17 $\endgroup$ Oct 17, 2011 at 21:41
  • $\begingroup$ @Gerhard: I don't know about that case, but there is a significant theory of whether the complete graph can be decomposed into copies of some specified graph. There are lots of theorems but also lots of open problems. Put "graph decomposition" (with the quotes) into google scholar. Someone who could tell you about the case of prisms is Darryn Bryant. $\endgroup$ Oct 18, 2011 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.