Prove that if $deg (v) > \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian.

Question

Let $G$ be a bipartite graph with partite sets $U$ and $W$ such that $|U|=|W|=k \geq 2$. Prove that if $deg (v) > \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian.

Dirac's theorem : Let $G$ be a graph of order $n$ such that $deg(v) \geq \frac {n}{2}$ for every vertex $v$ in $G$ then $G$ is Hamiltonian.

here is my proof

Let $G$ be a bipartite graph with partite sets $U$ and $W$ such that $|U|=|W|=k \geq 2$. . Since $G$ be a bipartite graph with partite sets $U$ and $W$ such that $|U|=|W|=k \geq 2$, $G$ has order $2k $. Let $V(U)=\{u_1, \dots, u_k\}$ and $V(W)=\{w_1, \dots, w_k\}$ Assume that $G$ isn't Hamiltonian. I still need the claim that $G$ is connected. Let $P$ be the maximum path in $G$, so we have $P$ is the zig zag path start from $u_1$ and end at $w_k$. Since $deg(v) \geq \frac {k}{2}$ for every vertex $v$ in $G$, $u_1$ must adj to some vertex $v_i$ and $v_k$ must adj to some vertex $u_i$ for $1<i<k$. And we stiil find a Hamiltonian cycle . So it's impossible to graph $G$ without containing a Hamiltonian cycle.

Answer 1

This proof is modeled after a rather standard proof of Dirac's theorem. Unfortunately it is longer than I expected it to be. Maybe I am overlooking something.

Claim 1: $G$ is connected.

Proof of claim 1: each vertex is adjacent to more than $\frac k2$ vertices in the other partite set, so even the smallest component has more than $k$ vertices. Since there are only $2k$ vertices altogether, there can be only one component.

Claim 2: Let $P$ be a maximal path and assume $P$ has $2m+1$ vertices. Then there cannot be a cycle with $2m$ vertices.

Proof of claim 2: Assume $C$ is a cycle with $2m$ vertices. If there is a vertex not on $C$ that has a neighbour that is not on $C$, we find a path of length at least $2m+2$. Contradiction. So every vertex that is not on $P$ has all its neighbours on $C$. Since $C$ has as many vertices of $U$ as of $W$, there is a vertex $u\in U$ and a vertex $w\in W$ that are both not on $C$. They both have more than $\frac k2$ different neighbours on $C$ and since $C$ has $2m<2k$ vertices, two of them must be adjacent(!), say $x$ (neighbour of $u$) and $y$ (neighbour of $w$). But then again we find a path of length $2m+2$ (start at $u$, go to $x$, take the long road on $C$ to $y$, then go to $w$). This last contradiction proves claim 2.

Claim 3: There cannot be a maximal path with $2m+1$ vertices.

Proof of claim 3: Assume there is such a maximal path $P$. We may assume it has $m+1$ vertices in $U$ and $m$ in $W$. Label the vertices $u_0,w_1,u_1,\ldots,w_m,u_m$. Now both $u_0$ and $u_m$ have more than $\frac k2$ neighbours on $P$ (or $P$ would not be maximal) and they are all among $w_1,\ldots,w_m$. If $u_0$ is adjacent to $w_i$, then $u_m$ cannot be adjacent to $w_{i-1}$, because we would find a cycle of $2m$ vertices, contradicting claim 2. So, since $u_0$ has more than $\frac k2$ neighbours on $P$ (among the $w_i$), $u_m$ has at least at least (not 'more' but 'at least' to cover for $w_0$) $\frac k2$ nonneighbours on $P$ (among the $w_i$), but then it cannot have $k$ neighbours on $P$ (among the $w_i$), since $m<k$. Contradiction.

Now the last two claims are just more of the same type of argument and I leave the proofs to you.

Claim 4: Let $P$ be a maximal path of $2m$ vertices, then $G$ has a cycle of $2m$ vertices.

Proof of claim 4: Assume there is no such cycle. The vertices on $P$ alternate among the parts. Label them $u_1,w_1,\ldots,u_m,w_m$. $u_1$ has at least $\frac k2$ neighbours among the $w_i$. If $w_i$ is a neighbour of $u_1$, then $u_i$ cannot be a neighbour of $w_m$ (or we find a cycle of length $2m$). Since $u_1$ has at least $\frac k2$ neighbours among the $w_i$, $w_m$ has at least $\frac k2$ nonneighbours among the $u_i$. But then it cannot have more than $\frac k2$ neighbours among the $u_i$ since $m\leq k$. Contradiction.

Claim 5: Let $P$ be a maximal path and assume $P$ has $2m$ vertices. If there is a cycle with $2m$ vertices, then $m=k$.

Proof of claim 5: Let $C$ be a cycle with $2m$ vertices. If there is a vertex $v$ that is not on $C$ there is a path from $v$ to $C$ and we can cut open the cycle to get a longer path. Contradiction. So every vertex is on the cycle and we are done.

Together the claims prove your exercise. Let me know if there are parts that you are unable to finish.

Answer 2

Start by assuming, to the contrary, that there exist graphs meeting the conditions yet are not Hamiltonian. Of all of these such graphs that act as counter examples to our theorem, let G be one of maximal size (i.e. that the addition of any edge will result in a Hamiltonian cycle). Let x be a vertex in U and let y be a vertex in W and let these two vertices be non adjacent. Then, xy cannot be an edge or it will produce a Hamiltonian cycle in G. Thus, there must be an x-y Hamiltonian path in G.

Now, let u* be a vertex in u adjacent to y, then u* cannot be adjacent to a vertex adjacent to x or else there will be a Hamiltonian cycle (this detail still needs to be ironed out, but I'm quite sure that, with a little bit more precision, this fact is true). Thus, Deg u* <= k-deg x. but deg x >n/2, so deg u* is less than k/2. This is a contradiction, and so it must be the case that the result holds.