Een algemene methode

Stel dat er een netwerk N gegeven is, en daarin een aantal paren punten waartussen informatie moet worden uitgewisseld via paden in het netwerk. Bepaal dan voor elk van die paren punten een pad tussen die punten met zo weinig mogelijk tussenpunten. (Hier kun je soms meerdere mogelijkheden hebben waartussen je dan een keuze mag en moet maken.) Neem deze paden als de punten van een nieuwe graaf G en bepaal de lijnen van G door na te gaan welke paden minstens één lijn gemeen hebben; dit is de padgraaf bij N voor de gekozen paden.

Dan geldt:

Het minimale aantal golflengtes dat nodig is om de communicatie in N te maken is precies het chromatische getal van de bijbehorende padgraaf G.

Opdracht 27