GRAPH THEORY-6

HAMILTONIAN CIRCUITS 

A Hamiltonian circuit in a connected graph is defined as a closed walk that traverses every vertex of G exactly once, except of course the starting vertex, at which the walk also terminates.

OR

A circuit in a connected graph G is said to be Hamiltonian if it includes every vertex of G. Hence a Hamiltonian circuit in a graph of n vertices consists of exactly n edges.

-------------------------------------------------------------------------------------

Hamiltonian Path: If we remove any one edge from a Hamiltonian circuit, we are left with a path. This path is called a Hamiltonian path. Clearly, a Hamiltonian path in a graph G traverses every vertex of G

Complete Graph: A simple graph in which there exists an edge between every pair of vertices is called a complete graph. 

Complete graphs of two, three, four, and five vertices are shown below