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?



Decomposition of $K_{10}$ in copies of the Petersen graph
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$.


