(a) Prove that if G is a simple graph with n ($n \ge 3$) vertices and…

Question

(a) Prove that if G is a simple graph with n ($n \ge 3$) vertices and if $d(v) \ge \frac{n}{2}$ for each vertex v, then G is Hamiltonian.

(b) Determine the shortest path from a to h of the following directed graph using Dijkstra's algorithm:

Related pages

• Hamiltonian Graphs — topic
• Discrete Mathematics syllabus