thumb|upright|Le graphe de Harborth répond au problème de trouver un graphe-allumettes dont tous les sommets sont de degré 4. En mathématiques, plus particulièrement en théorie des graphes, un graphe-allumettes est un graphe connexe dont il est possible de donner une représentation dans le plan euclidien en représentant toutes les arêtes par des segments de même longueur et ne se croisant jamais.
Lien avec les graphes distance-unité Un graphe-allumettes est un graphe à la fois distance-unité (au sens large) et planaire ; la réciproque est fausse comme le montrent les exemples du graphe prisme triangulaire et du graphe de Moser qui possèdent une représentation distance-unité et une représentation planaire mais pas de représentation ayant les deux propriétés simultanément.
Exemples de graphes-allumettes Les graphes chaine, les graphes grille, les graphes cycle, les graphes étoile. Le graphe de Harborth. Les graphes planaires connexes ayant une représentation où les faces sont des triangles équilatéraux identiques, comme le graphe triangle, le graphe diamant, le graphe papillon, le graphe roue W7 (qui est le seul graphe roue à être distance-unité). Les graphes planaires connexes ayant une représentation où les faces sont des losanges identiques, comme les graphes de Jahangir, les rosaces rhombiques ou certains pavages de Penrose. Dénombrements vignette|Les 5 graphes-allumettes à 4 arêtes : graphe chaine, graphe fourche, graphe étoile , graphe patte, graphe carré . Le nombre de graphes-allumettes à arêtes à isomorphisme près est donné par la . +1234567891011351228742076332008 Par exemple, les trois graphes-allumettes à trois arêtes sont le graphe chaine, le graphe étoile , et le graphe triangle.
Le nombre de graphes-allumettes à arêtes à homéomorphisme près est donné par la . +12345678910113510193984196479 Le nombre de graphes-allumettes à sommets à isomorphisme près est donné par la . +12345611251350 Références
Voir aussi
Graphe distance-unité Théorème de Fáry (tout graphe planaire peut être tracé avec des arêtes rectilignes, mais pas forcément de même longueur)
Catégorie:Famille de graphes