Poussin graf

Poussin graf
Vertices	15
Kanter	39
Radie	3
Diameter	3
Omkrets	3
Automorfismer	2 ( Z / 2Z )
Kromatiskt nummer	4
Kromatiskt index	6
Egenskaper	Hamiltonian Planar
Tabell över grafer och parametrar

Kempe- kedjor i Poussin-grafen. Gränserna mellan områdena på denna karta bildar Poussin-grafen, delvis fyrfärgad med den yttre regionen ofärgade. De blå-gula och blå-gröna Kempe-kedjorna (gula och gröna linjer) förbinder den yttre regionens grannar, så Kempe skulle byta färger i den vänstra röd-gula kedjan och den högra röd-gröna kedjan (röda linjer), vilket tillåter den yttre regionen att vara röd. När de blå-gula och blå-gröna kedjorna korsas, skulle detta färgbyte göra att de övre gula och gröna områdena båda blir röda, vilket ger en ogiltig färg.

I grafteorin är Poussin-grafen en plan graf med 15 hörn och 39 kanter. Den är uppkallad efter Charles Jean de la Vallée-Poussin .

Historia

1879 publicerade Alfred Kempe ett bevis på fyrafärgssatsen , en av de stora gissningarna inom grafteorin . Även om satsen är sann, är Kempes bevis felaktigt. Percy John Heawood illustrerade det 1890 med ett motexempel, och de la Vallée-Poussin nådde samma slutsats 1896 med Poussin-grafen .

Kempes (felaktiga) bevis är baserat på alternerande kedjor , och eftersom dessa kedjor visar sig vara användbara i grafteorin förblir matematiker intresserade av sådana motexempel. Fler hittades senare: först Errera-grafen 1921, sedan Kittell-grafen 1935, med 23 hörn, och slutligen två minimala motexempel (Soifer-grafen 1997 och Fritsch- grafen 1998, båda av ordning 9).

externa länkar

• Eric W. Weisstein , Poussin Graph ( MathWorld )