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.


  • 3
    $\begingroup$ Anton: all 3-regular graphs have an even number of vertices. $\endgroup$ Oct 18, 2011 at 6:45
  • 9
    $\begingroup$ Why would having an even number of vertices be an embarrassment to 3-regular graphs? $\endgroup$ Oct 18, 2011 at 6:56
  • 7
    $\begingroup$ In particular this graph is the smallest simple cubic graph with no perfect matching. $\endgroup$ Oct 18, 2011 at 13:40
  • 5
    $\begingroup$ As mentioned in mathworld.wolfram.com/PerfectMatching.html , 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. $\endgroup$ Oct 18, 2011 at 14:56
  • 4
    $\begingroup$ It deserves a better name than that. $\endgroup$ Oct 18, 2011 at 15:01

1 Answer 1


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.


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.