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$$.