Pósa's Theorem

There are several related theorems involving Hamiltonian cycles of graphs that are associated with Pósa.

Let be a simple graph with graph vertices.

1. If, for every in , the number of graph vertices of vertex degree not exceeding is less than , and

2. If, for odd, the number of graph vertices with vertex degree not exceeding is less than or equal to ,

then contains a Hamiltonian cycle.

Kronk (1969) generalized this result as follows. Let be a simple graph with graph vertices, and let . Then the following conditions are sufficient for to be -line Hamiltonian:

1. For all integers with , the number of graph vertices of vertex degree not exceeding is less than ,

2. The number of points of degree not exceeding does not exceed .

Pósa (1963) generalized a result of Dirac by proving that every finite simple graph with a sufficiently large valencies of all (or, in some cases, of almost all) vertices and with a sufficiently large number of vertices satisfies one of the following conditions.

1. has a Hamiltonian line containing all edges of given disjoint paths (Theorem 1),

2. has a circuit with a "large" number of vertices (Theorems 2 and 3), or

3. has a "small" number of disjoint circuits containing all vertices of the graph (Theorems 4 and 5).