Voir la source de 20-graphe de Thomassen

{{Infobox Graphe
 | nom                = 20-Graphe de Thomassen
 | image              = 
 | légende            = 
 | distribution       = 3 (15  sommets)<br />4 (4 sommets)<br />5 (1 sommet)
 | sommets            = 20
 | arêtes             = 33
 | automorphismes     = 
 | maille             = 5
 | diamètre           = 4
 | rayon              = 3
 | nombre chromatique = 3
 | indice chromatique = 5
 | propriétés         = [[Graphe hypohamiltonien|Hypohamiltonien]]
}}
Le '''20-graphe de Thomassen''' est, en [[théorie des graphes]], un graphe possédant 20 sommets et 33 arêtes.

== Propriétés ==

=== Propriétés générales ===
Le [[Diamètre (théorie des graphes)|diamètre]] du 20-graphe de Thomassen, l'excentricité maximale de ses sommets, est 4, son [[Rayon (théorie des graphes)|rayon]], l'excentricité minimale de ses sommets, est 3 et sa [[Maille (théorie des graphes)|maille]], la longueur de son plus court [[cycle (graphe)|cycle]], est 5. Il s'agit d'un graphe 3-[[Graphe sommet-connexe|sommet-connexe]] et d'un graphe 3-[[Graphe arête-connexe|arête-connexe]], c'est-à-dire qu'il est [[graphe connexe|connexe]] et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

=== Coloration ===
Le [[nombre chromatique]] du 20-graphe de Thomassen est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'[[indice chromatique]] du 20-graphe de Thomassen est 5. Il existe donc une 5-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

=== Propriétés algébriques ===
Le [[polynôme caractéristique]]    de la [[matrice d'adjacence]] du 20-graphe de Thomassen est : <math>(x-2) (x-1)^4 (x+2)^3 (x^2-3) (x^2-2 x-1) (x^3+2 x^2-3 x-2) (x^5-12 x^3-6 x^2+23 x+14)</math>.

== Voir aussi ==

=== Liens internes ===
* [[Théorie des graphes]]
* le [[32-graphe de Thomassen]]
* le [[34-graphe de Thomassen]]
* le [[41-graphe de Thomassen]]
* le [[60-graphe de Thomassen]] 
* le [[94-graphe de Thomassen]] 
* le [[105-graphe de Thomassen]]

=== Liens externes ===
* {{en}} [[Eric W. Weisstein]], [http://mathworld.wolfram.com/ThomassenGraphs.html Thomassen Graphs] ([[MathWorld]])

=== Références ===
<references />

{{Portail|Mathématiques}}

[[Catégorie:Graphe remarquable|Thomassen (20)]]