Regulær graf av grad 3

[skf95]

Hvis jeg har en regulær graf av grad 3, bestående av [tex]n[/tex] noder, med omkrets [tex]5[/tex]; er da [tex]n[/tex] delelig med [tex]5[/tex]?

Hvis ikke; er [tex]n[/tex] delelig med [tex]5[/tex] hvis grafen består av kun ringer med omkrets [tex]5[/tex], altså kun består av femkanter (slik som petersen-grafen)?

• Regulær graf; alle nodene er av samme grad
• Grad; "antall kanter ut fra noden"
• Omkrets; korteste "ringen" i grafen

[Gustav]

Det fins en 3-regulær graf med 12 noder der den korteste ringen er 5:

http://en.wikipedia.org/wiki/File:Graph ... 034891.jpg

PS: er du sikker på at omkretsen av en graf er definert som den korteste ringen, og ikke den lengste?

På mathworld er de engelske uttrykkene girth (korteste ring) og circumference (lengste ring)

http://mathworld.wolfram.com/Girth.html

http://mathworld.wolfram.com/GraphCircumference.html