# Has anyone seen this graph?

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.

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.

Thanks

• Anton: all 3-regular graphs have an even number of vertices. – David Eppstein Oct 18 '11 at 6:45
• Why would having an even number of vertices be an embarrassment to 3-regular graphs? – Mariano Suárez-Álvarez 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 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. – Sergey Norin Oct 18 '11 at 14:56
• It deserves a better name than that. – David Eppstein Oct 18 '11 at 15:01