În teoria graficelor , o ramură a matematicii , un grafic cub este un grafic regulat de gradul 3. Cu alte cuvinte, este un grafic în care există exact trei muchii incidente la fiecare vârf.
O consecință a lemei de strângere de mână este că fiecare grafic cub are un număr par de vârfuri.
Conform teoremei lui Brooks , vârfurile unui grafic cub pot fi colorate cu trei culori (sau mai puțin), astfel încât două vârfuri adiacente să nu aibă aceeași culoare, cu excepția cazului graficului tetraedric .
Un grafic bicubic este un grafic bipartit regulat de gradul 3, adică un grafic cub ale cărui vârfuri pot fi colorate cu doar două culori.
Graficul complet este singurul grafic cub care necesită 4 culori
Colorarea graficului Frucht cu 3 culori
este un grafic bicubic, sunt suficiente 2 culori
Marginile grafului Petersen, un snark, au nevoie de 4 culori
Conform teoremei lui Vizing , muchiile unui grafic cub pot fi colorate cu 3 sau 4 culori fără ca două margini de aceeași culoare să fie incidente la același vârf. De snarks sunt legate grafice cubi fără istm care au nevoie de 4 culori.
Teorema lui Petersen afirmă că orice grafic cub fără istmul are o potrivire perfectă .
Cu alte cuvinte, dacă, într-un grafic cub, orice margine aparține unui ciclu, atunci există un set de margini care sunt incidente la toate vârfurile, fiecare vârf fiind doar capătul uneia dintre aceste margini.
Această teoremă, una dintre cele mai vechi din teoria graficelor, din 1891, este văzută astăzi ca o aplicație a teoremei tuturor (în) .
Un exemplu de potrivire perfectă într-un grafic necubic
Marginile roșii formează o cuplare perfectă a graficului Petersen.
Teorema a fost generalizată: o presupunere, formulată de Michael D. Plummer și László Lovász spune că orice grafic cub fără istm are un număr exponențial de cuplaje perfecte . Această conjectură a fost demonstrată de Esperet, Kardoš, King și Kráľ în 2011.
Într-un grafic hamiltonian , putem parcurge toate vârfurile o singură dată.
Majoritatea graficelor cubice sunt hamiltonieni, dar nu toți: probabilitatea de a fi hamiltoniană tinde la 1 atunci când numărul vârfurilor crește la nesfârșit.
Graficele cubice pot fi chiar poliedrice , cubice și non-hamiltoniene în același timp , așa cum arată graficul tuturor . Ele pot fi, de asemenea, atât bicubice, cât și non-hamiltoniene, așa cum se arată în graficul Horton sau în graficul Ellingham-Horton 54 . Conjectura Barnette (în) , încă nedovedită și nu invalidată în prezent spune că fiecare grafic atât poliedrică bicubic și ar Hamiltonian.
Când un grafic cub este hamiltonian, notația LCF îi permite să fie reprezentată concis.
Un ciclu hamiltonian în graficul dodecaedric
Bidiakis cubul , reprezentat în așa fel încât să evidențieze că este poliedrică
Cubul Bidiakis, aranjat diferit: cercul evidențiază un ciclu hamiltonian