Question

Tick all graphs that have a Hamiltonian path. Select one or more: None of the graphs have a Hamilton path. K1,4,1

Answer 1

According to Ore’s Theorem:

            Consider a general tripartite case G = K _l,m,n For 1 <= l<= m<=n. and K_l,m,n has a Hamiltonian path if and only if l + m >= n.

For the Hamiltonian path, you can show that Graph G has a Hamiltonian path if and only if the graph H Create by adding an extra vertex to a G adjacent to all vertices of G has a Hamiltonian cycle. Then by essentially the same argument can be used, to show that H has a Hamiltonian cycle if and only l + m >= n-1, and thus G has a Hamiltonian path if and only if l + m >= n-1.

So for the tripartite Graph K _l,m,n It has Hamiltonian path if and only if

l + m >= n-1 -----> eq.1

1. K _2,2,4   -> here l = 2, m = 2, n = 4, according to ore’s theorem it should satisfy above eq.1
   • 2 + 2 >= 4 -1 -> 4 >= 3
   • So K _2,2,4 has a Hamiltonian Path.
2. K _1,2,3   -> here l = 1, m = 2, n = 3, according to ore’s theorem it should satisfy above eq.1
   • 1 + 2 >= 3 -1 -> 3 >= 2
   • So K _1,2,3 has a Hamiltonian Path.
3. None of the above is not the answer.
4. K _1,4,1   -> here l = 1, m = 4, n = 1, according to ore’s theorem it should satisfy above eq.1
   • 1 + 4 >= 1 -1 -> 4 >= 0
   • So K _1,4,1 has a Hamiltonian Path.
5. K _2,1,2   -> here l = 2, m = 1, n = 2, according to ore’s theorem it should satisfy above eq.1
   • 2 + 1 >= 2 -1 -> 3 >= 1
   • So K _2,1,2 has a Hamiltonian Path.