Given a complete bipartite graph of $K_{m,n}$, assume $n \geq m \geq 1$. Prove that every cycle contained in the $K_{m,n}$ has at most $2m$ vertices.

315 Views Asked by At

When trying to solve this question, I use an example where $n = 4$, $m = 3$ which gives us:
$n + m$ vertices $\implies$ $4 + 3 = 7$ vertices
$nm$ edges -> $4 \cdot 3 = 12$ edges
However, the confusion begins when $K(m,n)$ has at most $2m$ vertices because $2(3) = 6$ which is less than the $7$ vertices defined above. The potential error that I thought about was that I accidentally swapped the $n$ and $m$ variables, however, the condition of $n \geq m \geq 1$ was given. Another fundamental problem that I may have is that my understanding of Cycles in a Complete Bipartite Graph may be flawed or misunderstood. Lastly, I've drawn the complete bipartite graph myself for a visualization aid and I believe the structure is correct.

I hope my logic and reasoning make sense and I would love clarification and instruction on how to go about this proof.

1

There are 1 best solutions below

0
On BEST ANSWER

Firstly, the problem is poorly phrased. You can have as many vertices in a cycle as you like if you go around the same cycle over and over again. So, I assume the question is really about "simple cycles" (which don't pass through the same vertex twice). Every second vertex in a cycle is contained in the side with $m$ vertices. Since the cycle cannot have duplicate vertices, the total number of vertices is at most $2m.$