MTH4140 Home

Hamiltonian Graphs

Definition

Definition

Assume that \(G=(V,E)\) is a graph. A Hamiltonian path is a sequence of vertices \((v_1, v_2, \dots, v_n)\) such that every two consecutive vertices are connected with an edge and every vertex from \(V\) appears exactly once in the sequence.

If the graph also contains an edge between the first and the last vertex (\(v_1\) and \(v_n\)) of Hamiltonian path, then the sequence \((v_1, v_2, \dots, v_n)\) is called a Hamiltonian cycle.

The graph that has Hamiltonian cycle is called a Hamiltonian graph.

Theorem 1

Assume that \(G\) is a graph that has a proper coloring with two colors red and green. Then the number of green vertices must be equal to the number of red vertices.

Theorem 2 (Ore's theorem)

Assume that \(G=(V,E)\) is a simple graph with \(n\) vertices. If for every two vertices \(u\) and \(v\) that satisfy \((u,v)\not\in E\) the sum of the degrees satisfies \(d(u)+d(v)\geq n\) then \(G\) has a Hamiltonian cycle.

Problem

There are \(100\) guests in a hotel. Each guest has at most \(49\) enemies among the remaining guests. Prove that it is possible to put guests in \(50\) double rooms in such a way that no-one is in a room with an enemy.

Remark: If \(A\) is and enemy of \(B\) than \(B\) is also an enemy of \(A\).