22
$\begingroup$

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


(source: uci.edu)

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)?

$\endgroup$
1

2 Answers 2

23
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Any two bridges lie on a path, so the second theorem is a strengthening of the first, not a converse. $\endgroup$ Jun 1, 2012 at 3:53
  • $\begingroup$ Oops! It's fixed. $\endgroup$ Jun 1, 2012 at 5:02
-1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ @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. $\endgroup$ May 30, 2012 at 15:30
  • $\begingroup$ 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? $\endgroup$ May 30, 2012 at 15:32
  • $\begingroup$ @Anthony, pick your favourite cubic graph and substitute each vertex with a triangle. You get a claw free cubic graph. $\endgroup$ May 30, 2012 at 15:33
  • $\begingroup$ @Gjergji Zaimi: Oh, right, I had overlooked the induced subgraph part ;-) Thanks! $\endgroup$ May 30, 2012 at 15:38
  • $\begingroup$ Sorry for the wrong answer... $\endgroup$ Jun 1, 2012 at 10:20

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.