# Unique matching completion

Assume we have bridgeless cubic graph $G(V, E)$, $n=|V|$. By Petersen's theorem, every such graph has a perfect matching. Moreover, given any edge in $G$ there exists a perfect matching containing this edge. I am interested in finding the size $|C|$ of the smallest set of vertex-disjoint edges $C$ that uniquely determines a perfect matching $M$ (i.e. $C \subset M$).

Notice that every cubic bridgeless graph G has at least $\Omega (2^{|V(G)|/3656})$ perfect matchings.

What is the minimum number of vertex-disjoint edges $|C|$ that uniquely force any perfect matching in any bridgeless cubic graph?

Equivalently, a subset $C$ of a perfect matching $M$ is called a forcing set if $M$ is the unique perfect matching containing $C$. The forcing number of $M$ is the minimum cardinality of forcing sets of $M$. The forcing number of a cubic bridgeless graph $G(V, E)$ is the minimum number of forcing numbers of all perfect matchings of $G$. So my questions becomes:

What is the forcing number for any bridgeless cubic graph?

I guess a constant is not enough. I guess that we need at least $|C|=\Omega( n)$ and $O(\log n)$ is not enough. Is there a proof?

• I can understand this question in two ways: (1) what is the minimal $k$ such that in SOME (bridgeless cubic) graph there are $k$ edges uniquely defining a matching; or (2) what is the minimal $k$ such that in ANY (bridgeless cubic) graph there are $k$ edges uniquely defining a matching. Which one are you interested in? – Ilya Bogdanov Apr 15 '17 at 22:34
• @IlyaBogdanov The second one. I just edited the post. – Mohammad Al-Turkistany Apr 15 '17 at 22:53
• It may be worth noting that in the first sense (1) of @IlyaBogdanov 's comment, the number $k = 1$. An example is a circular ladder, where we modify one rung to "turn" it parallel to the ladder. (see Figure 1 arxiv.org/pdf/1012.2878.pdf) – Harry Richman Oct 12 '17 at 11:03

Take a circular ladder of odd length. Also known as the cartesian product of $C_n$ ($n$ odd) and $K_2$. For every perfect matching there are many ways to change it into a different perfect matching by replacing two edges by another two (these four edges forming a 4-cycle). I didn't work out the exact details, but it seems you can't specify one perfect matching exactly by giving less than about $\frac13 n$ edges, while there is one choice of about $\frac13 n$ edges that suffices. For even $n$, there is another type of perfect matching (not using any rungs) that can be uniquely specified by giving two edges.