Hamiltonian Graphs And Semi Hamiltonian Graphs

Hamiltonian Graphs

Definition: A graph $G = (V(G), E(G))$ is considered Hamiltonian if and only if the graph has a cycle containing all of the vertices of the graph.

Definition: A Hamiltonian cycle is a cycle that contains all vertices in a graph $G$. If a graph has a Hamiltonian cycle, then the graph $G$ is said to be Hamiltonian.

For example, let's look at the following graphs (some of which were observed in earlier pages) and determine if they're Hamiltonian.

Graph Type	Graph	Hamiltonian or Not?
Complete Graph $K_5$		Hamiltonian. Notice that a cycle can easy be formed since all vertices $x_i$ are connected to all other vertices in $V(G)$.
Complete Graph $K_6$		Hamiltonian. Same case as above.
Complete Bipartite Graph $K_{2,3}$		Not Hamiltonian.
Complete Bipartite Graph $K_{3,3}$		Hamiltonian. Recall that a cycle of a complete bipartite graph uses the same number of vertices from vertex set $A$ and vertex set $B$. If we want to consider Hamiltonian graphs for complete bipartite graphs, then if $V(G) = A \cup B$ and $A \cap B = \varnothing$, then | A | = | B |.
Disconnected Graph		Not Hamiltonian. This should be rather obvious since a cycle cannot be formed containing all vertices of the graph!
Graphs with Leaves		Not Hamiltonian. The degree of all vertices in a cycle is $2$, but the degree of vertex $x_1$ that is considered a leaf by definition has $\deg (x_1) = 1$. Thus a cycle cannot be formed.
Cube Graph $Q_3$		Hamiltonian. In fact, $Q_k$ for all $k$ is Hamiltonian. (See Gray Codes)
Cycle Graph $C_6$		Hamiltonian. It should be obvious that a cycle graph in itself contains a Hamiltonian cycle. In fact, the graph is a Hamiltonian cycle.
Platonic Solid: Octahedron		Hamiltonian. All platonic solids are Hamiltonian.

Determining if a Graph is Hamiltonian

Unlike determining whether or not a graph is Eulerian, determining if a graph is Hamiltonian is much more difficult. Dirac's and Ore's Theorem provide a suitable condition though.