Math 2.0

statement theorem

Dirac's theorem on Hamiltonian cycles

Statement

Let GG be a finite simple graph with n≥3n \ge 3 vertices. Suppose that every vertex of GG has degree at least n/2n/2. Then GG is Hamiltonian.

Remarks

The hypothesis says that the minimum degree is at least n/2n/2. The theorem follows from Ore's theorem: if all degrees are at least n/2n/2, then each sum of two degrees is at least nn. The bound is sharp. The complete bipartite graph Kk,k+1K_{k, k+1} has minimum degree k<(2k+1)/2k < (2k+1)/2, and it is not Hamiltonian.

History

G. A. Dirac published the theorem in 1952.

Explanations

L1 human

If each vertex is joined to at least half of the other vertices, there is a round trip through all vertices. A graph with this many edges cannot avoid a Hamiltonian cycle.

What this node needs for W1
  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 11 nodes in this order. The foundations come first, and the list ends with this node.

Graph, definition, no evidence levelGraphdefinitionNeighbourhood, definition, no evidence levelNeighbourhooddefinitionWalk, definition, no evidence levelWalkdefinitionDegree of a vertex, definition, no evidence levelDegree of a vertexdefinitionTrail, definition, no evidence levelTraildefinitionMinimum degree, definition, no evidence levelMinimum degreedefinitionCircuit, definition, no evidence levelCircuitdefinitionCycle, definition, no evidence levelCycledefinitionHamiltonian cycle, definition, no evidence levelHamiltonian cycledefinitionHamiltonian graph, definition, no evidence levelHamiltonian graphdefinitionDirac's theorem on Hamiltonian cycles, statement, no evidence levelDirac's theorem on Ha…statement
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Graph definition
  2. Neighbourhood definition
  3. Walk definition
  4. Degree of a vertex definition
  5. Trail definition
  6. Minimum degree definition
  7. Circuit definition
  8. Cycle definition
  9. Hamiltonian cycle definition
  10. Hamiltonian graph definition
  11. Dirac's theorem on Hamiltonian cycles statement

Sources

  1. Web https://en.wikipedia.org/wiki/Hamiltonian_path, Bondy–Chvátal theorem

What links here

No node links to this node yet.