Bipartite graph with exactly one perfect matching

Question

$\textbf{Problem:}$ Find all bipartite graphs $G[X,Y]$ satisfying the following properties:

$1.$ $|X|=|Y|$, where $|X|\ge 2$ and $|Y|\ge 2$.

$2.$ All vertices have degree three except for two vertices in $X$ and two vertices in $Y$, which have degree two.

$3.$ $G$ has exactly one perfect matching.

$\textbf{My approach:}$ By trying out some examples it seems fair enough to conjecture that there doesn't exist such a graph $G$. I haven't yet found a proof to the above conjecture, but for the sake of contradiction if I assume that there exists such a graph $G$, then it seems that the bipartiteness of $G$ along with property $1$ and $2$ would end up with $G$ having at least two distinct perfect matchings, a contradiction to property $3$.

There is a very close result to the above problem which states the following:

Let $G[X,Y]$ be a bipartite graph on $2n$ vertices in which all vertices have degree three except for one vertex in $X$ and one vertex in $Y$, which have degree two. Then $pm(G)\ge 2(4/3)^{n-1}$, where $pm(G)$ is the number of perfect matchings in $G$.

Is there any way to use this result to solve the above problem? Actually, even any kind of hint to proceed along my lines of approach would be of great help. Thanks!

Answer 1

There are indeed no such bipartite graphs. In fact:

Proposition. Let $G=(X,Y,E)$ be a bipartite graph with $n:=|X|=|Y|$ in which the degree of each vertex is at least $2$ and at most $3$. Then, $G$ has either no perfect matching or at least two perfect matchings.

Observation. Under the hypotheses of the proposition, the number of degree-$2$ vertices is the same in $X$ and $Y$. (Count the number of edges in $G$ as $\sum_{x\in X}d(x)$ or as $\sum_{y\in Y}d(y)$, and equate the two expressions.)

Proof of the proposition. We use induction on $n$. The base is when $n=2$, in which case the claim is trivial, because the only bipartite graph satisfying the condition is the cycle of length $4$.

Let $n>2$, and suppose, for the sake of getting a contradiction, that $G$ has exactly one perfect matching. Then, $G$ satisfies Hall's condition, and moreover, there is a set $\varnothing\neq A\subsetneq X$ which is critical, in the sense that $|N(A)|=|A|$, where $N(A)$ is the set of neighbors of the vertices in $A$. Namely, if no critical set exists, then Hall's condition remains satisfied even if we remove a single edge from the graph (in particular, one of the edges of the perfect matching), and this contradicts the uniqueness of the perfect matching.

Note that if $A$ is a critical set, then the vertices of $A$ are necessarily matched with $N(A)$, and the vertices in $X\setminus A$ are necessarily matched with $Y\setminus N(A)$. Moreover, every critical set in our graph has at least two vertices.

Let $A$ be a minimal critical set. Let $k$ denote the number of degree-$2$ vertices in $A$, and $\ell$ the number of degree-$2$ vertices in $N(A)$. Again, a counting argument shows that $k\geq\ell$, and there are exactly $k-\ell$ vertices between $N(A)$ and $X\setminus A$.

Let $Q$ denote the set of vertices in $N(A)$ that have at least one neighbor in $X\setminus A$, that is $Q:=N(A)\cap N(X\setminus A)$. Note that for every $y\in Q$, $d(y)=3$ and there is exactly one edge between $y$ and $X\setminus A$. Indeed, if this is not the case, then $y$ is connected to exactly one vertex $x\in A$. But then $A\setminus\{x\}$ will also be a critical set, contradicting the minimality of $A$.

It follows that in the subgraph $G'$ which is induced on $A\cup N(A)$, the degree of each vertex is at least $2$ and at most $3$. Therefore, by the induction hypothesis, $G'$ has either no perfect matching or at least two perfect matchings. In either case, this leads to a contradiction because we already know that $A$ can be matched with $N(A)$ and $X\setminus A$ can be matched with $Y\setminus N(A)$. $\square$