Decomposition of $K_{10}$ in copies of the Petersen graph

2012-02-08T12:51:08Z

It is a well-known and cute exercise in algebraic graph theory to show that $K_{10}$ cannot be written as the edge-disjoint union of three copies of the Petersen graph $P$. Indeed, the graph $G$ whose edge-set is the complementary of the two copies of $P$ in $K_{10}$ is a $3$-regular bipartite graph. When I taught this, the classroom discussion went as follows:

Q: Can we compute the spectrum of $G$. A: Well we could always compute a 10x10 determinant but (I am going to regret this if I don't know how to do it) I think we can do much better. Q: How? A: OK, let me be honest, I have no idea, but I am hoping that $G$ will turn out to be a well-known graph.

And indeed, we wrote down a decomposition of $K_{10}$ for which $G$ turned out to be the connected bipartite 3-regular circulant graph on ten vertices $Z$ (the spectrum then being very easy to compute).

Left silent in this discussion was whether this was the only possibility. I do believe it is. Indeed, unless I am mistaken (something which is alas entirely possible), $G$ is by construction a 3-regular bipartite connected graph on ten vertices. Beside, the two copies of $P$ share an eigenvector $v$ for the eigenvalue 1 so $v$ is an eigenvector for the eigenvalue $-3$ of $G$. Thus, $v$ has values in ${\pm 1}$ and gives the bipartition on $G$. From this, it follows that the set of vertices on which $v$ takes the value $1$ (resp. $-1$) is a 5-cycle. On each vertex, the third edge of each copy of $P$ thus connects the first $C_{5}$ to the second. Let $H$ be the graph whose edge set is given by the edges of the $P$ between the cycles. The graph $G$ is then the complementary graph of $H$ in the complete bipartite graph $K_{5,5}$. The graph $H$ is by construction 2-regular and bipartite, hence either $C_{10}$ or the union of $C_{4}$ and $C_{6}$. In both cases, there is a bijection between vertices of $H$ and triplets of vertices of $H$ which sends a vertex $w$ to the three vertices in the other bipartition class which are not adjacent to $w$. Hence, $G$ does not have two pairs of vertices with the same neighborhoods. But there are only two 3-regular bipartite connected graph on ten vertices, one has two pairs of vertices with the same neighborhoods and the other is $Z$.

However, the above is deeply unsatisfying to me, if only because I don't trust my capacities to really enumerate all the possible ways to fit two copies of $P$ in $K_{10}$ at all, so that I am unconvinced that I did not make a mistake in the above. Moreover, the punchline of the argument is a classification of bipartite regular 3-connected graphs on ten vertices, something I can do only via a tedious enumeration (or by looking it up).

Is there a conceptual way to show that the decomposition as two copies of $P$ and $Z$ is the only possible one (provided the above is correct)?

More specifically, is it possible to compute the spectrum, or the automorphism group of $G$, or perhaps even a large subgroup of the automorphism group of $G$ without relying on long(ish) enumerations?

Answer by Chris Godsil for Decomposition of $K_{10}$ in copies of the Petersen graph

2012-02-08T15:05:24Z

Assume $A_1$ and $A_2$ are the adjacency matrices of two edge-disjoint copies of Pete in $K_{10}$. Since Pete has an eigenvalue 1 with multiplicity 5, and since this eigenspace is in the orthogonal complement of the all-ones vector, the intersection $\ker(A_1-I)\cap\ker(A_2-I)$ is not trivial. Let $z$ be a non-zero vector in it. Then $(A_1+A_2)z=2z$ and, if $A_0=J-I-A_1-A_2$, then $A_0z=-3z$. Since $A_0$ is the adjacency matrix of a cubic graph $G$, we see that $G$ must be bipartite. (This all standard, is in my book with Royle, and goes back to Allen Schwenk, I believe.)

Now the complement of $G$ in $K_{5,5}$ is a 2-regular bipartite graph, hence it is either $C_{10}$ or $C_4\cup C_6$. The only problem is to eliminate the second case, which your argument with triplets does.

Decomposition of $K_{10}$ in copies of the Petersen graph - MathOverflow

Decomposition of $K_{10}$ in copies of the Petersen graph

Answer by Chris Godsil for Decomposition of $K_{10}$ in copies of the Petersen graph