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

Question

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 1

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.

Answer 2

The general picture is as follows. Let $\mathcal P_{i}$ be an edge-disjoint decomposition of $K_{10}$ in 3 3-regular graphs with $\mathcal P_{1,2}$ isomorphic to the Petersen graph. Then there exists two eigenvectors common to all three $\mathcal P_{i}$: the indicatrix of $K_{10}$ and one associated with the eigenvalues $1$ for the two copies Petersen graph and $-3$ for $\mathcal P_{3}$. The sum and difference of these common eigenvectors suitably normalized are respectively the indicatrix of two subsets of 5 vertices inducing a 2-regular graph, hence a 5-cycle, in $\mathcal P_{i}$ for $i=1,2$. Hence, the two copies of the Petersen graph is completely described by the choice of fixed-point free permutation $\sigma$ of $\mathfrak S_{5}$ corresponding to the choice of edges of $\mathcal P_{2}$ given the identification of vertices in the 2 5-cycles given by the edges of $\mathcal P_{2}$ (or more intrinsically by the choice of two elements $\sigma,\tau$ in $\mathfrak S_5$ such that $\sigma\tau^{-1}$ is fixed point free). One can obtain in this way two non-isomorphic graphs depending on whether $\sigma$ admits a 2-cycle or not.

Hence $\mathcal P_{3}$ can indeed be the complementary of $C_{10}$ in $K_{5,5}$ or the complementary of $C_4\cup C_6$.