The Circumference and Girth of a Graph
The Circumference and Girth of a Graph
Definition: For a graph $G = (V(G), E(G))$, the Circumference of a graph refers to the length of the longest cycle in the graph. The Girth of a graph refers to the length of the shortest cycle in the graph. |
For example, let's look at the graph below:
By inspection, we should see that the smallest cycle that can be formed is of length $3$, and the largest cycle that can be formed is of length $4$:
Hence the girth of the graph is $3$, and the circumference of the graph is $4$.