Extension of Peterson Theorem with exactly k exceptions.

624 Views Asked by At

The Peterson Theorem: If $G$ a connected graph is cubic (each vertex has exactly 3 neighbors) and bridgeless (If we cut one edge, $G'$ obtained still connected) then $G$ has a perfect matching.

Now the question is: If we lower the condition "bridgeless" to: There are exactly $k$ edges such that if we cut one of these edges $G'$ obtained is not connected anymore. For which values of $k$ does $G$ admit a perfect matching?

2

There are 2 best solutions below

0
On

I found counterexamples when $k\geq 3$ now for k=1 It is true by recalling the proof of Peterson. for k =2 I'm still stuck.

0
On

Cubic graphs with fewer than $3$ bridges have a perfect matching: A 3-regular graph with fewer than 3 bridges has a perfect matching.

For any $k\ge3$, we can construct an unmatchable cubic graph with exactly $k$ bridges by inserting $k-3$ copies of the following subgraph on $4$ vertices into the classic unmatchable cubic graph.

subgraph on 4 vertices

For example, the following graph is cubic, has exactly $5$ bridges, and is unmatchable by applying Tutte's condition to the vertex incident to $3$ bridges.

unmatchable cubic graph with exactly 5 bridges