Math 2.0

definition

Hamiltonian graph

Definition

A graph is Hamiltonian if it has a Hamiltonian cycle.

Remarks

The cycle graph CnC_n and the complete graph KnK_n for n≥3n \ge 3 are Hamiltonian. A tree is not Hamiltonian, because it has no cycle. The Petersen graph is not Hamiltonian. Dirac's theorem and Ore's theorem give sufficient conditions in terms of degrees.

Explanations

L1 human

A graph is Hamiltonian when you can visit all of its vertices in one round trip, each vertex once. Many edges make this easier, and this is the idea of the theorems of Dirac and Ore.

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 7 nodes in this order. The foundations come first, and the list ends with this node.

Graph, definition, no evidence levelGraphdefinitionWalk, definition, no evidence levelWalkdefinitionTrail, definition, no evidence levelTraildefinitionCircuit, definition, no evidence levelCircuitdefinitionCycle, definition, no evidence levelCycledefinitionHamiltonian cycle, definition, no evidence levelHamiltonian cycledefinitionHamiltonian graph, definition, no evidence levelHamiltonian graphdefinition
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. Walk definition
  3. Trail definition
  4. Circuit definition
  5. Cycle definition
  6. Hamiltonian cycle definition
  7. Hamiltonian graph definition

What depends on this

2 nodes use this node, directly or through other nodes.

Sources

  1. Web https://en.wikipedia.org/wiki/Hamiltonian_path, Definitions

What links here

Used by