# Graph circuit

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

An edge progression containing all the vertices or edges of a graph with certain properties. The best-known graph circuits are Euler and Hamilton chains and cycles. An edge progression (a closed edge progression) is an Euler chain (Euler cycle) if it contains all the edges of the graph and passes through each edge once. There exists an effective criterion for the existence of Euler cycles (Euler's theorem): A connected graph has an Euler cycle if and only if each of its vertices (except two) has even degree.

An edge progression (closed edge progression) is called a Hamilton chain (Hamilton cycle) if it contains all the vertices of the graph and if it passes through each of them once. Several conditions sufficient for the existence of Hamilton cycles are known, such as: The graph has no loops or multiple edges and, for any two of its non-adjacent edges, the sum of their degrees is not less than the number of vertices in the graph; the graph is planar and quadruply-connected; the graph has no loops or multiple edges, and the number of its vertices and of its edges satisfy the conditions and . A graph is said to be Hamiltonian (Eulerian) if it has a Hamilton (Euler) cycle. A graph is said to be Hamilton-connected if any two of its vertices are connected by a Hamilton chain, and is said to be -Hamiltonian if any simple chain of length forms part of some Hamilton cycle. The well-known "travelling-salesman problemtravelling-salesman problem" is to find in a graph with edges labeled with non-negative numbers (lengths of edges) a Hamilton cycle with the smallest sum of edge lengths. This problem and other problems of graph circuits have various technological and economic applications.

#### References

 [1] F. Harary, "Graph theory" , Addison-Wesley (1969) [2] A.A. Zykov, "The theory of finite graphs" , 1 , Novosibirsk (1969) (In Russian)