If the bridges of a $3$-regular graph $G$ lie on a single path then $G$ has a $1$-Factor (perfect matching)

46 Views Asked by At

If the bridges of a $3$-regular graph $G$ lie on a single path then $G$ has a $1$-Factor (perfect matching)

I've proved that a $3$-regular graph with at most two bridges has a perfect matching ($1$-factor), and I also know that a bridgeless $3$-regular graph has a $1$ factor, however I'm a bit lost here and I don't really see how to use the fact that the bridges lie on a single path. I tried to look at the $2$-connected components of $G$ and try to add a vertex to make each of these blocks $3$-regular so that each block has a $1$ factor but I think this doesn't really work. So any help would be greately appreciated.

1

There are 1 best solutions below

0
On

Proceed by induction on the number of bridges. If there are at most two bridges, we are done. Suppose now that $G$ has $k\geq 3$ bridges, say $b_1, \dots, b_k$, labelled in order of the path. Deleting these yields subgraphs $C_1, \dots, C_{k+1}$, with the natural labelling.

Construct two new graphs, to which we will apply the induction hypothesis, as follows. Let $H$ be obtained from $K_4$ by subdividing an edge. Let $G'$ be obtained from $G[\cup_{i=1}^{k-1}V(C_i)]$ by adding a copy of $H$ and an edge between the vertex of degree two in the copy of $H$ and the vertex of degree two in $C_{k-1}$. Analogously, let $G''$ be obtained from $G[\cup_{i=k}^{k+1}V(C_i)]$ by adding a copy of $H$ and an edge between the vertex of degree two in the copy of $H$ and the vertex of degree two in $C_{k}$. Essentially $G'$ is $G$ where we have replaced the last two subgraphs by a copy of $H$, and $G''$ is $G$ where we replaced the first $k-2$ subgraphs by a copy of $H$.

Now, $G'$ has $k-1$ bridges on a path, $G''$ has $2$ bridges, and both $G'$ and $G''$ are cubic. By induction, $G'$ has a perfect matching $M'$ and $G''$ a perfect matching $M''$. Moreover, since $H$ has an odd number of vertices, $M'$ and $M''$ both contain the bridge to their respective copies of $H$. Thus, the matching $M$ obtained by taking all edges in $M'$ not in the copy of $H$, together with all edges in $M''$ not in the copy of $H$, and $b_{k-1}$, forms a perfect matching of $G$, as desired.

I believe this a theorem due to Alfred Errera from 1922, but I do not know if this is the proof he gave.