Polyhedrální graf je neorientovaný graf vytvořený z vrcholů a hran konvexního mnohostěnu nebo, v kontextu teorie grafů, rovinného grafu se 3 vrcholy .
Schlegelův diagram konvexního mnohostěnu představuje jeho vrcholy a hrany jako body a úsečky na euklidovské rovině , tvořící rozdělení vnějšího konvexního mnohoúhelníku na menší konvexní mnohoúhelníky. Diagram nemá žádné průsečíky, takže jakýkoli polyedrický graf je také rovinný . Také podle Balinského teorému je tento graf spojen s vrcholem 3 .
Podle Steinitzovy věty tyto dvě vlastnosti postačují ke kompletnímu popisu polyedrických grafů – jsou to přesně 3-vrcholově spojené rovinné grafy. Pokud je tedy graf rovinný i 3-vrcholově spojený, existuje mnohostěn, jehož vrcholy a hrany tvoří graf izomorfní k původnímu [1] [2] . Vzhledem k takovému grafu lze jeho znázornění jako rozdělení konvexního mnohoúhelníku na menší konvexní mnohoúhelníky nalézt pomocí Tuttova vložení [3] .
Tate se domníval , že jakýkoli kubický polyedrický graf (tj. polyedrický graf, ve kterém každý vrchol dopadá přesně na tři hrany) má hamiltonovský cyklus , ale tuto domněnku vyvrátil William Tutt , který zkonstruoval protipříklad – nehamiltonovský polyedrický graf. ( graf Tatta ). Povolíme-li podmínku, že graf musí být kubický, objeví se mnoho dalších menších nehamiltonských polyedrických grafů, jedním z nich s 11 vrcholy a 18 hranami je Herschelův graf [4] , existuje i nehamiltonovský polyedrický graf s 11 vrcholů, ve kterých jsou všechny plochy trojúhelníkové - Goldnerův graf - Harari [5] .
Přísně vzato, existuje konstanta ( exponent krátkosti[ upřesnit ] ) a nekonečnou rodinu polyedrických grafů takovou, že délka nejdelší jednoduché cesty grafu s vrcholy v rodině je [6] [7] .
V roce 1996 byl stanoven počet polyedrických grafů do 26 hran [8] , konkrétně počet takových grafů s 6, 7, ..., 21 hranami je:
1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810 [9] .Polyedrické grafy můžete také vyčíslit počtem jejich vrcholů, počet takových grafů je:
1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, … [10] .Polyhedrální graf je jednoduchý polytopový graf, pokud je kubický (tři hrany se sbíhají v každém vrcholu), a je to jednoduchý polytopový graf, pokud je maximální rovinný graf . Halinovy grafy , vytvořené z rovinných stromů přidáním vnější smyčky přes všechny listy stromu, tvoří další důležitou podtřídu polyhedrálních grafů.