Decomposition of a complete graph into maximal matching subgraphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T01:52:31Z http://mathoverflow.net/feeds/question/78385 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78385/decomposition-of-a-complete-graph-into-maximal-matching-subgraphs Decomposition of a complete graph into maximal matching subgraphs helvio 2011-10-17T21:11:57Z 2011-10-17T21:20:39Z <p>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?</p> <p>For example, consider $K_4$ with vertices $V=${1,2,3,4}. It can be decomposed into the union:</p> <p>$K_4=$ {{1,2},{3,4}} $\cup$ {{1,3},{2,4}} $\cup$ {{1,4},{2,3}}</p> <p>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:</p> <p>$K_n= \bigcup_\sigma$ { {$\sigma(1),\sigma(n-1)$}, {$\sigma(2),\sigma(n-2)$}, ... }</p> <p>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.</p> http://mathoverflow.net/questions/78385/decomposition-of-a-complete-graph-into-maximal-matching-subgraphs/78386#78386 Answer by Gerry Myerson for Decomposition of a complete graph into maximal matching subgraphs Gerry Myerson 2011-10-17T21:20:39Z 2011-10-17T21:20:39Z <p>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}$. </p>