A Proof on Hamiltonian Complete Bipartite Graphs | Graph Theory, Hamiltonian Graphs

Which complete bipartite graphs are Hamiltonian? We'll prove the answer to that question in today's graph theory lesson!

A little bit of messing around with complete bipartite graphs might present the answer to you. The complete bipartite graph Kmn (m vertices in one partite set and n vertices in the other) is Hamiltonian if and only if m = n and both m and n are greater than or equal to 2.

We will prove both directions of this biconditional theorem and it should be good fun! All we have to do for one direction is identify a Hamiltonian cycle to prove the graph is Hamiltonian. For the other direction, the existence of a Hamiltonian cycle will quickly lead to the partite sets needing to have the same number of vertices!

Remember a complete bipartite graph is a bipartite graph where any two vertices in different partite sets are adjacent. A Hamiltonian cycle in a graph is a cycle containing all vertices of the graph, if a graph has such a cycle then it is a Hamiltonian graph.

Basically explained, this theorem is true because a Hamiltonian cycle in a bipartite graph must go back and forth from one partite set to the other, since all edges join vertices in different partite sets. Thus it must visit the same number of vertices in one partite set as it does in the other partite set. Then, since it visits all vertices of the graph (by definition of Hamiltonian), the partite sets have the same cardinality (as in, m = n).



I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / seanemusic