Bipartite graph with exactly one perfect matching.

376 Views Asked by At

$\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!

1

There are 1 best solutions below

0
On

It might help you. See Gjergji Zaimi's response at MathOverflow and Hall's article