Nella teoria dei grafi, il calibro (in inglese girth) di un grafo è la lunghezza del ciclo più corto contenuto nel grafo.^[1] Se il grafo non contiene alcun ciclo (è cioè un grafo aciclico), il suo calibro si definisce infinito.^[2] Ad esempio, un ciclo di ordine 4 (quadrato) ha calibro 4. Anche una griglia ha calibro 4, e una maglia triangolare ha calibro 3. Un grafo con calibro pari a 4 o superiore è senza triangoli.

Un grafo cubico (tutti i vertici hanno grado 3) di calibro ${\displaystyle g}$ – cioè più piccolo possibile – è noto come una gabbia ${\displaystyle g}$ o come una gabbia (3,${\displaystyle g}$). Il grafo di Petersen è l'unica gabbia 5 (è il più piccolo grafo cubico di calibro 5), il grafo di Heawood è l'unica gabbia 6, il grafo di McGee è l'unica gabbia 7 e il grafo di Tutte-Coxeter è l'unica gabbia 8.^[3] Possono esistere gabbie multiple per un dato calibro. Per esempio ci sono tre gabbie 10 non isomorfiche, ognuna con 70 vertici: la gabbia 10 di Balaban, il grafo di Harries e il grafo di Harries-Wong.

• 
  Il grafo di Petersen ha un calibro di 5
• 
  Il grafo di Heawood ha un calibro di 6
• 
  Il grafo di McGee ha un calibro di 7
• 
  Il grafo di Tutte-Coxeter (gabbia 8 di Tutte) ha un calibro di 8

Per un qualsiasi intero positivo ${\displaystyle g}$ e ${\displaystyle \chi }$, esiste un grafo con un calibro almeno di ${\displaystyle g}$ e un numero cromatico almeno di ${\displaystyle \chi }$; ad esempio, il grafo di Grötzsch è senza triangoli e ha numero cromatico 4, e ripetendo la costruzione di Jan Mycielski usata per formare il grado di Grötzsch produce grafi senza triangoli con numero cromatico arbitrariamente grande. Paul Erdős fu il primo a provare il risultato generale, usando il metodo probabilistico.^[4] Più precisamente, dimostrò che un grafo aleatorio su ${\displaystyle n}$ vertici, formato scegliendo indipendentemente se includere ogni bordo con probabilità ${\displaystyle n^{(1-g)/g))$, ha, con probabilità che tende a 1 quando ${\displaystyle n}$ va a infinito, al massimo ${\displaystyle n/2}$ cicli di lunghezza ${\displaystyle g}$ o minore, ma non ha alcun insieme indipendente di dimensione ${\displaystyle n/2k}$. Perciò, eliminare un vertice da ogni ciclo corto lascia un grafo più piccolo con calibro maggiore di ${\displaystyle g}$, in cui ogni classe di colore di una colorazione deve essere piccola e che quindi richiede almeno ${\displaystyle k}$ colori in una qualsiasi colorazione.

Il calibro dispari e il calibro pari di un grafo sono le lunghezze rispettivamente del più breve ciclo dispari e del più breve ciclo pari.

Pensato come la minore lunghezza di un ciclo non banale, il calibro ammette generalizzazioni naturali come sistole 1 o sistoli superiori in geometria sistolica.

• (EN) Computing the girth of a graph (PDF), su webcourse.cs.technion.ac.il, Technion, 31 dicembre 2013. URL consultato il 28 dicembre 2012.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica