Rešetka (teorija grafova)

Rešetka, vrsta grafa u teoriji grafova. To je regularan graf s najnmajim mogućim brojem vrhova koji je stupnja [math]\displaystyle{ \Delta }[/math] i struka [math]\displaystyle{ g }[/math] zove se [math]\displaystyle{ (\Delta,g) }[/math]-rešetka. Među prvim znanstvenicima koji su proučavali ovu vrstu grafova spada W. T. Tutte. Pál Erdős i Horst Sachs poslije su dokazali [math]\displaystyle{ (\Delta,g) }[/math]-rešetke postoje za sve [math]\displaystyle{ \Delta\geq }[/math] 2 i [math]\displaystyle{ g\geq 3 }[/math]. Ova vrsta grafova je vrlo rijetka. Do danas je dokazano postojanje 38 ovakvih grafova i to za koje vrijedi [math]\displaystyle{ \Delta\leq 14 }[/math] i [math]\displaystyle{ g\leq 12 }[/math].