2
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Sure (this is more or less what I wrote in the question, I think). But my argument with triplets only work if one knows that there are only two connected 3-regular bipartite graphs on 10 vertices and that one has the wrong kind of neighborhoods. This I know only by enumerating the 19 possible connected 3-regular graphs on 10 vertices. It is for this last step that I am wondering if a conceptual argument exists (after all, ex post, we know that $G$ has a large automorphism group; perhaps there is a way to see it ex ante). $\endgroup$
    – Olivier
    Feb 8, 2012 at 15:26
  • $\begingroup$ But if we know the graph left over is bipartite and cubic, there are only two possible graphs. I do not see why the 19 connected cubic graphs are relevant? I very much doubt that it is possible to use the automorphism group in any useful way. $\endgroup$ Feb 9, 2012 at 0:31
0
$\begingroup$

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

$\endgroup$

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.