$\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
    $\begingroup$ Can you show that the graph has a cycle? If it does, it must be a cycle on an even number of vertices and on those vertices, there are two perfect matchings.... (What is the source of this problem?) $\endgroup$ Aug 6 at 13:35
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/4217756/37830 $\endgroup$
    – Algernon
    Aug 6 at 14:34
  • $\begingroup$ The graph must have a cycle, since otherwise there would be vertex of degree one. $\endgroup$ Aug 6 at 17:27

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$

  • $\begingroup$ Thanks for this. I have just one question, did you assume $G$ to be a simple bipartite graph, or did you assume it to be any bipartite graph? $\endgroup$ Aug 15 at 20:11
  • $\begingroup$ I have assumed that $G$ is simple, but I believe the same holds if you allow multiple edges. The proof goes through with minor adaptations (the induction starts at $n=1$, etc.) $\endgroup$
    – Algernon
    Aug 15 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.