b'\n_START_ARTICLE_\nKubi\xc4\x8dni graf\n_START_PARAGRAPH_\nK\xc3\xbabi\xc4\x8dni gr\xc3\xa1f je v teoriji grafov graf v katerem imajo vse to\xc4\x8dke stopnjo enako 3 in je tako 3-regularni graf. Kubi\xc4\x8dni graf se imenuje tudi tr\xc3\xadval\xc3\xa9ntni graf._NEWLINE_B\xc3\xadk\xc3\xbabi\xc4\x8dni gr\xc3\xa1f je kubi\xc4\x8dni dvodelni graf.\n_START_SECTION_\nSimetrija\n_START_PARAGRAPH_\nLeta 1932 je Ronald Martin Foster za\xc4\x8del zbirati primere kubi\xc4\x8dnih simetri\xc4\x8dnih grafov in sestavil Fosterjev popis. Veliko znanih posameznih grafov je kubi\xc4\x8dnih in simetri\xc4\x8dnih. Med njimi so najbolj znani: graf napeljav, Petersenov, Heawoodov, M\xc3\xb6bius-Kantorjev, Paposov, Desarguesov, Naurujski, Coxetrov, Tutte-Coxetrov, Dyckov, Fosterjev in Biggs-Smithov. William Thomas Tutte je klasificiral simetri\xc4\x8dne kubi\xc4\x8dne grafe glede na najmanj\xc5\xa1e tak\xc5\xa1no celo \xc5\xa1tevilo s, da se lahko vsaki usmerjeni povezavi z dol\xc5\xbeino s preslikajo druga v drugo s to\xc4\x8dno eno simetrijo grafa. Pokazal je, da je s lahko najve\xc4\x8d 5 in podal primere grafov za vsako mo\xc5\xbeno vrednost s od 1 do 5._NEWLINE_Med polsimetri\xc4\x8dne kubi\xc4\x8dne grafe spadajo: Grayjev (najmanj\xc5\xa1i polsimetri\xc4\x8dni kubi\xc4\x8dni graf), Jofinove in Ivanova, Ljubljanski in Tuttejeva 12-kletka._NEWLINE_Fruchtov graf je eden od dveh najmanj\xc5\xa1ih kubi\xc4\x8dnih grafov brez simetrije - ima le en avtomorfizem, enotski avtomorfizem.\n_START_SECTION_\nBarvanje in neodvisne mno\xc5\xbeice\n_START_PARAGRAPH_\nPo Brooksovem izreku se lahko vsak kubi\xc4\x8dni graf razen polni graf  pobarva z najve\xc4\x8d tremi barvami. Tako ima vsak kubi\xc4\x8dni graf razen  neodvisno mno\xc5\xbeico vsaj  to\xc4\x8dk, kjer je  \xc5\xa1tevilo to\xc4\x8dk v grafu: najve\xc4\x8dji barvni razred v 3-barvanju ima vsaj toliko to\xc4\x8dk._NEWLINE_Po Vizingovem izreku se za barvanje povezav potrebuje tri ali \xc5\xa1tiri barve. 3-to\xc4\x8dkovno-barvanje je znano kot Taitovo barvanje in tvori particijo to\xc4\x8dk grafa v tri popolna parjenja. Po K\xc5\x91nigovem izreku o barvanju povezav ima vsak bikubi\xc4\x8dni graf Taitovo barvanje._NEWLINE_Kubi\xc4\x8dni grafi brez mostov, ki nimajo Taitovega barvanja, so znani kot snarki. Najbolj znani snarki so: Petersenov graf, Tietzejev graf, Blanu\xc5\xa1eva snarka, cvetli\xc4\x8dni snark, snark dvojna zvezda, Szekeresov snark in Watkinsov snark. Obstaja neskon\xc4\x8dno mnogo razli\xc4\x8dnih snarkov.'