Encyclopedia > Girth

  Article Content


In graph theory, the girth of a graph is the length of the shortest cycle contained in the graph. If the graph doesn't contain any cycles, its girth is defined to be infinity.

For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3.

The Heawood graph in the figure on the left is the smallest trivalent graph with girth 6; the Petersen graph on the right is the smallest trivalent graph with girth 5.

In common usage, girth refers to the circumference of a cylindrical object such as a tree trunk

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
List of people by name: Ma

... Marilyn, (born 1969), US musician Manstein, Erich von, (1887-1973), Field Marshal Mantegna, Andrea, (c.1431-1506), Italian painter Mantel, Hilary[?], English ...