# Cubic graphs without a perfect matching and a vertex incident to three bridges

The example shown below (courtesy of David Eppstein) is a common example of a cubic graph that admits no perfect matching:

Are there other examples of cubic graphs that do not admit a perfect matching and, unlike the above example, do not contain a vertex that lies at the intersection of three bridges (i.e. an edge whose removal increases the number of connected components in the graph)?

Substitute your central vertex in your graph with a 3-cycle $abc$ so that the graph stays cubic. Now subdivide each edge in this 3-cycle. So we have new vertices $u$ connected to $a$ and $b$, $v$ connected to $b$ and $c$, $w$ connected to $c$ and $a$. Now add a final vertex $x$ and connect it to $u,v$ and $w$. This graph has exactly three bridges, none of which intersect the other at a vertex, and moreover has no perfect matching!

One result which relates the existence of a perfect matching in a cubic graph and its bridges is the following theorem of Petersen from "Die theorie der regularen graphen", Acta Math. 15 (1891), 163-220:

Theorem: Every cubic graph with at most two bridges contains a perfect matching.

As well as this strengthening by Errera, "Du colorage des cartes", Mathesis 36 (1922), 56-60:

Theorem: If all the bridges of a connected cubic graph $G$ lie on a single path of $G$, then $G$ has a perfect matching.

So your instinct is true, in the sense that if the graph has no perfect matching, its bridges do not lie on a path. However the example in the beginning of this answer shows that they are not necessarily incident at the same vertex.

• Any two bridges lie on a path, so the second theorem is a strengthening of the first, not a converse. – Brendan McKay Jun 1 '12 at 3:53
• Oops! It's fixed. – Gjergji Zaimi Jun 1 '12 at 5:02

I think there are no such graphs.

It was shown by Sumner and Las Vergnas (you can find the references here: http://mathsci.kaist.ac.kr/~sangil/pdf/2009claw.pdf) that a claw-free connected graph has a perfect matching (assuming even number of vertices, of course!). An intersection of three bridges is clearly a claw.

• @Felix: What you are saying is that: no perfect matching implies there is a claw. But a claw does not necessarily imply three bridges. So this does not address the question. – Gjergji Zaimi May 30 '12 at 15:30
• This is surely simple, but given that every vertex in a cubic graph has by definition three neighbours, how can any cubic graph be claw-free? – Anthony Labarre May 30 '12 at 15:32
• @Anthony, pick your favourite cubic graph and substitute each vertex with a triangle. You get a claw free cubic graph. – Gjergji Zaimi May 30 '12 at 15:33
• @Gjergji Zaimi: Oh, right, I had overlooked the induced subgraph part ;-) Thanks! – Anthony Labarre May 30 '12 at 15:38
• Sorry for the wrong answer... – Felix Goldberg Jun 1 '12 at 10:20