1
$\begingroup$

Let $G$ be a bridgeless cubic (simple) graph, and let $M$ be a perfect matching in $G$. $G-M$ will necessarily be a set of circuits. For example, if we delete a perfect matching from $K_{3,3}$ we end up with one circuit. If we delete a perfect matching from the Petersen graph we end up with two circuits. And in general, one could end up with many. The following question comes to mind.

Question Let $G$ be a cubic bridgeless (simple) graph which is cyclically edge-5-connected, and let $M$ be a perfect matching in $G$. Is there a subset $K$ of edges in $M$ such that $G-K$ has exactly two components, such that either none of the two components are circuits, or both are circuits?

For example, any perfect matching in the Petersen graph is an example of such an edge cut.

A graph $G$ is cyclically edge-5-connected if no set of fewer than 5 edges is cycle separating. A set $K$ of edges is cycle separating if $G-K$ is disconnected and at least two of its components contain circuits.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .