Circuit

Definition

A circuit in graph theory is a path that starts and ends at the same vertex with no other repeated vertices. It is a closed loop in a graph where each edge is used exactly once.

5 Must Know Facts For Your Next Test

1. A circuit must start and end at the same vertex.
2. No vertices, except for the starting/ending vertex, can be repeated in a circuit.
3. Every edge in a circuit is unique and used only once.
4. A circuit with all vertices included exactly once is called a Hamiltonian circuit.
5. Eulerian circuits traverse every edge of the graph exactly once without repetition.

Review Questions

• What distinguishes a circuit from other types of paths in a graph?
• Can a circuit contain repeated vertices? Why or why not?
• Explain the difference between an Eulerian circuit and a Hamiltonian circuit.

Related terms

Path: A sequence of edges which connect a sequence of vertices.

Hamiltonian Circuit: A circuit that visits each vertex exactly once before returning to the starting vertex.

Eulerian Circuit: A circuit that traverses every edge of the graph exactly once, starting and ending at the same vertex.