Homework SourseGraph theory problem Let G be a bipartite graph with partite
Graph theory problem:
Let G be a bipartite graph with partite sets U and V such that |U| = |W| = k 2. Prove that if deg(v) > k/2 for every vertex v of G, then G is Hamiltonian.
Graph theory problem:
Let G be a bipartite graph with partite sets U and V such that |U| = |W| = k 2. Prove that if deg(v) > k/2 for every vertex v of G, then G is Hamiltonian.
Let G be a bipartite graph with partite sets U and V such that |U| = |W| = k 2. Prove that if deg(v) > k/2 for every vertex v of G, then G is Hamiltonian.
Solution
Since G be a bipartite graph with partite sets U and W such that |U|=|W|=k2, G has order 2k. Let V(U)={u1,…,uk} and V(W)={w1,…,wk} Assume that G isn\'t Hamiltonian. Let P be the maximum path in G, so we have P is the zig zag path start from u1 and end at wk. Since deg(v)k2 for every vertex v in G, u1 must adj to some vertex vi and vk must adj to some vertex ui for 1<i<k. And we stiil find a Hamiltonian cycle . So it\'s impossible to graph G without containing a Hamiltonian cycle. Hence G is hamiltonian.
