girth

(graph theory:)

The girth of a graph is the size of its smallest cycle. For instance, any cube or hypercube has girth 4 (and any bipartite graph will of course have a girth that is even or infinite).

A celebrated theorem of Pál Erdős states that there exist graphs with arbitrarily large girth and chromatic number. This theorem was the basis of the probabilistic method.

Girth (?), n. [Icel. gjor girdle, or ger girth; akin to Goth. ga�xa1;rda girdle. See Gird to girt, and cf. Girdle, n.]

1.

A band or strap which encircles the body; especially, one by which a saddle is fastened upon the back of a horse.

2.

The measure round the body, as at the waist or belly; the circumference of anything.

He's a lu sty, jolly fellow, that lives well, at least three yards in the girth. Addison.

3.

A small horizontal brace or girder.

© Webster 1913.

Girth, v. t. [From Girth, n., cf. Girt, v. t.]

To bind as with a girth.

Johnson.

© Webster 1913.