Share
Explore BrainMass

Hamiltonian and Nonhamiltonian Graphs

4.15 Show that this theorem 1 is sharp, that is, show that for infinitely many n>=3 there are non-hamiltonian graphs G of order n such that degu+degv>=n-1 for all distinct nonadjacent u and v.

Can you explain this theorem,please

Theorem1: If G is a graph of order n>=3 such that for all distinct nonadjacent vertices u and v, deg v +deg u >=n then G is hamiltonian.

Can you explain it step by step and draw a graph.

Solution Preview

For any n>=3, we construct a nonhamiltonian graph G of order n such that degu+degv>=n-1 for all distinct nonadjacent u and v. The graph is as follows.
First, we select n-2 nodes and construct a complete graph H with n-2 nodes.
Then, we select a node u in H, and other two single nodes v,w not in H.
Then, we set an edge ...

Solution Summary

Hamiltonian and Nonhamiltonian Graphs are investigated.

$2.19