If $G(A,B,E)$ is a simple , connected bipartite graph with $n$ vertices in both of its vertex classes, and if we let the degrees in one class be different. How can we show that $G$ contains a perfect matching?
What I know from this information:
That $G$ has no loops so we can apply the first Gallai theorem : $\alpha + \tau = 2n$ (applied to this case). Also, since it is a bipartite we can use Konig's theorem : $\nu = \tau$ and $\alpha = \rho$ .
And if I am right the question basically asks either to show that $\nu = n$ or I need to show that $|A| = |B|$ and prove Hall's theorem for this $G$.
Now, my main question here is how can I apply Hall's theorem here to show that this graph $G(A,B,E)$ contains a matching covering $A$ or $B$?
I am not sure how can I show that $\forall x \subsetneq A :|N(x)| \leq |x|$ here.(Hall's theorem; $N$ refers to the neighborhood)
Any hint is greatly appreciated.
I suppose you can procede inductively. Since all vertices say in $A$ have different degrees and it is connected, then we have in $A$ vertex $v$ with degree $1$. Say it is connected with $u$ in $B$. Now repeat everything in $A'=A\setminus \{v\}$ (and $B'=B\setminus\{u\}$).
You can see that vertices in $A'$ have again different degrees ($u$ was connected to all vertices in $A$, othervise $G$ would not be connected graph).