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:

Screen%20Shot%202014-02-18%20at%201.08.25%20PM.png

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$:

Screen%20Shot%202014-02-18%20at%201.10.54%20PM.png

Hence the girth of the graph is $3$, and the circumference of the graph is $4$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License