Question

What theorem helps identify or determine the existence of a Hamiltonian circuit on a connected graph? ...


What theorem helps identify or determine the existence of a Hamiltonian circuit on a connected graph?
a.
Hamiltonian Theorem
b.
Daren’s Theorem
c.
Eulerian Graph Theorem
 
d.
Dirac’s Theorem

Answer

Dirac’s Theorem theorem helps identify or determine the existence of a Hamiltonian circuit on a connected graph

It can applied to any graph.

let the number of vertices is n then minimum degree is at least n/2 where it contain a Hamilton cycle.

Dirac's theorm also applied for chordal graphs.

It is also applied for k-connected graphs.

 

Dirac’s Theorem theorem helps identify or determine the existence of a Hamiltonian circuit on a connected graph

Option d correct

Recent Questions