Graf – to obiekt matematyczny składający się ze zbioru wierzchołków i zbioru krawędzi łączących w pary niektóre z tych wierzchołków. Grafy przedstawia się zwykle na płaszczyźnie za pomocą zbioru punktów odpowiadających wierzchołkom oraz linii łączących te punkty. Dość często linie te interpretuje się jako relacje między obiektami, reprezentowanymi przez punkty.

Dla przykładu, wyobraźmy sobie graf, w którym wierzchołki przypisane są ludziom, żyjącym obecnie na Ziemi (będzie spory, prawda?). Połączmy dwa wierzchołki linią, jeśli odpowiedni ludzie są znajomymi. Wprowadźmy teraz pojęcie odległości między osobami A i B, mierząc ją minimalną liczbą punktów, przez które trzeba przejść po grafie od człowieka A do człowieka B. Oczywiście, jeśli osoby A i B znają się między sobą (czyli odpowiadające im punkty sąsiadują na grafie), to owa odległość wynosi zero.

Powstaje teraz naturalne i interesujące pytanie: jaka maksymalna odległość dzieli dowolnych dwoje ludzi?

Panuje powszechne przekonanie, że ta odległość wynosi 6. Oznacza to na przykład, że każdy z nas ma znajomego, który ma znajomego (i to powtarza się sześć razy), …, który zna – powiedzmy – Billa Clintona, albo papieża. Istnieje przypuszczenie, że na przykład w USA (a to przecież spory kraj!) maksymalna odległość między ludźmi w tym sensie wynosi tylko 3.

Uzupełnienie:

Uogólnieniem pojęcia grafu jest multigraf, dopuszczający wiele równoległych krawędzi między tą samą parą wierzchołków, i hipergraf, o krawędziach będących dowolnymi, niekoniecznie dwuelementowymi, podzbiorami zbioru wierzchołków. Własności grafów bada teoria grafów. Jest ona bardzo istotna dla informatyki i nauk komputerowych.