MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I recently constructed the graph shown below in the process of investigating some problems regarding line graphs and homomorphisms, and then happened to see it on wikipedia. I was wondering if anyone knew of this graph coming up anywhere else.

enter image description here

If it helps, I was partly inspired by this paper which shows that any graph with maximum degree 3 and circular chromatic index 4 must contain $K_4$ with one edge subdivided as a subgraph. Note that the graph in the link above is three copies of $K_4$ with one edge subdivided plus another vertex which is adjacent to the vertices that are subdividing the edges.


share|cite|improve this question
Joel, I did contact David Eppstein before I posted here actually. He said that the main property that he knew it for was that it did not have a perfect matching, as opposed to bipartite or 2-connected cubic graphs. – David E. Roberson Oct 18 '11 at 6:37
Why would having an even number of vertices be an embarrassment to 3-regular graphs? – Mariano Suárez-Alvarez Oct 18 '11 at 6:56
In particular this graph is the smallest simple cubic graph with no perfect matching. – Andrew D. King Oct 18 '11 at 13:40
As mentioned in , this graph has been implemented in Mathematica as GraphData["NoPerfectMatchingGraph"]. This appears to confirm that the absence of perfect matchings is its most recognized property. – Sergey Norin Oct 18 '11 at 14:56
It deserves a better name than that. – David Eppstein Oct 18 '11 at 15:01

Any connected trivalent graph realises a Schreier coset graph of a subgroup of the modular group. This yields a transitive permutation group of degree 16 x 3 since we expand each node into an oriented triangle. In the original graph, switching the ends of edges & rotating the oriented triangles provides generators of order 2 and order 3. Recall PSL(2,Z) = free product C2 * C3.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.