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
Academy Award for Best Art Direction

... Inferno 1975 Ken Adam[?], Roy Walker[?], Vernon Dixon[?] - Barry Lyndon Edward Carfagno[?], Frank McKelvy[?] - The Hindenburg[?] Alexander Trauner[?], Tony ...