Bipartite graph which number of complete matching is $1$, has at least one $degree=1$ vertex?

Question

There is a bipartite graph $G = (U, V, E)$ which is $|U| = |V|$, and the number of complete matching is only $1$.
Is this graph always contain at least $1$ vertex that $deg(v) = 1 \ (v \in V)$?
If so, how to prove it?

Answer 1

The statement is trivally false if $|U|=|V|=0$, so assume otherwise.

Suppose by way of contradiction that each vertex in $V$ has degree $>1$. The complete matching of $G$ gives a bijection $f:V\to U$. For each $v\in V$ we can pick an edge $(v,g(v))$ with $g(v)\neq f(v)$ (note that $g$ need not be a bijection). Since $V$ is finite, the usual pigeonhole argument implies $(f^{-1}g)^n(v_0)=v_0$ for some $n>0$ and $v_0\in V$. Now define a new map $h:V\to U$ given by $$ h(v)=\begin{cases} g(v)&\text{if }v=(f^{-1}g)^i(v_0)\text{ for some }i,\\ f(v)&\text{otherwise}. \end{cases} $$ Note that $(v,h(v))$ is an edge for all $v\in V$. Also $h(v_0)=g(v_0)\neq f(v_0)$. Finally consider any $u\in U$. If $f^{-1}(u)=(f^{-1}g)^i(v_0)$ for some $i$ then $$ u=f\left((f^{-1}g)^{n+i}(v_0)\right) =g\left((f^{-1}g)^{n+i-1}(v_0)\right) =h\left((f^{-1}g)^{n+i-1}(v_0)\right). $$ Otherwise $u=f(f^{-1}(u))=h(f^{-1}(u))$. Thus $h$ is surjective, so it is a complete matching of $G$ distinct from $f$, contradicting the hypothesis.