Hamiltonian graph

1. Definition

1.1 Hamiltonian path & Hamiltonian circuit

• Passing diagram （ Undirected graph or directed graph ） A path in which all vertices in a are once and only once is called Hamiltonian path .
• Passing diagram （ Undirected graph or directed graph ） A circuit in which all vertices in a are once and only once is called Hamiltonian circuit .

1.2 Hamilton & Semi Hamiltonian graph

• A graph with a Hamiltonian loop is called Hamilton .
• A graph with a Hamiltonian path but without a Hamiltonian loop is called a graph Semi Hamiltonian graph .

【 notes 】 Specify that a trivial graph is a Hamiltonian graph .

2. nature

【 notes 】p(G) Express G The number of connected branches of .

• Set up undirected graph G = \lt V,E \gt It's a Hamiltonian graph , For any V_1 \subset V And V_1 \ne \varnothing , Both

\begin{array}{c} p(G-V_1) \leq |V_1| \end{array}

• Set up undirected graph G = \lt V,E \gt It's a semi Hamiltonian graph , For any V_1 \subset V And V_1 \ne \varnothing , Both

\begin{array}{c} p(G-V_1) \leq |V_1| + 1 \end{array}

• set up G yes n Order undirected simple graph , If for G Any nonadjacent vertex in u,v Both

\begin{array}{c} d(u) + d(v) \geq n-1 \end{array}

be G There is a Hamiltonian path in .

• set up G yes n(n \geq 3) Order undirected simple graph , If for G Any nonadjacent vertex in u,v Both

\begin{array}{c} d(u) + d(v) \geq n \end{array}

be G There is a Hamiltonian loop in .

• set up u,v by n Order undirected simple graph G Two nonadjacent vertices in , And d(u) + d(v) \geq n , be G Is a Hamiltonian graph if and only if G \cup (u,v) Is Hamiltonian graph .
• n(n \geq 2) There are Hamiltonian paths in every tournament of order .