I grafteori er en matchgraf en graf, der kan tegnes på et plan på en sådan måde, at alle dens kanter er linjestykker med længden et, og kanterne ikke skærer hinanden. Denne graf har således en indlejring i planet både som en enhedsafstandsgraf og som en plan graf . Uformelt set kan en matchgraf lægges ud af ikke-skærende tændstikker på en flad overflade , deraf navnet [1] .
Meget forskning i tændstikgrafer vedrører almindelige grafer , hvor hvert hjørne har det samme antal naboer. Dette tal kaldes grafens grad .
Det er kendt, at der er matchgrafer i alle grader op til den fjerde. Komplette grafer med et, to og tre hjørner (et enkelt toppunkt, en kant og en trekant) er tændstikgrafer, henholdsvis 0-, 1- og 2-regulære. Den mindste 3-regelmæssige tændstik-graf er dannet af to kopier af romber placeret således, at de tilsvarende spidser er i enhedsafstand. Dens dobbelte todelte dæksel er grafen af et ottekantet prisme med skæringspunkter [1] .
I 1986 præsenterede Heiko Harbort jarlen, som fik sit navn - Earl of Harbort . Med 104 kanter og 52 hjørner er denne graf det mindste kendte eksempel på en 4 -regulær matchgraf [2] . Grafen er stiv [3] .
Det er umuligt for en almindelig match-graf at have grader større end fire [4] .
Som vist af Kurtz og Mazukolo [5] har den mindste 3-regelmæssige trekantfri tændstik-graf (omkreds ≥ 4) 20 hjørner. Derudover præsenterede de det mindste kendte eksempel på en 3-regulær tændstikgraf med omkreds 5 (180 hjørner).
At kontrollere, om en given ikke- rettet plan graf kan repræsenteres som en tændstikgraf, er et NP-hårdt problem [6] [7]
Antallet af forskellige (op til isomorfi) matchgrafer er kendt op til ti kanter [8] [9] :
1, 1 , 3 , 5 , 12 , 28 , 74 , 207, 633, 2008, …