Encyclopedia > Girth

  Article Content

Girth

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
Fifteenth United States Congress

... United States Congress Fifteenth United States Congress This is currently a draft article. The text in this article is computer-generated. Links and spelling ...