Operacje na grafach
Operacje binarne
- Suma grafów Definicja:
- Przecięcie grafów Definicja:
- Zespolenie grafów Definicja:
.
Jeżeli dane są dwa grafy 
oraz 
, to ich sumą jest graf, którego zbiór wierzchołków i krawędzi tworzą wszystkie wierzchołki i krawędzie tych grafów.
.
Jest definowane analogicznie do sumy. Jeżeli dane są dwa grafy i , to ich przecięciem jest graf, którego wierzchołki i krawędzie wchodzą w skład obu tych grafów.
.
Zespoleniem grafów i nazywamy graf w którym z każdego wierzchołka G1 poprowadzono krawędzie do każdego wierzchołka G2.
Operacje unarne
- Graf krawędziowy grafu prostego G Graf który dla każdej krawędzi z G ma wierzchołek połączony z wierzchołkami reprezentującymi pozostałe krawędzie sąsiadujące ze sobą w G. Etapy konstrukcji grafu krawędziowego:
- Dopełnienie grafu Dopełnieniem grafu G nazywamy graf
- Graf dualny grafu G Graf, którego wierzchołki odpowiadają ścianom w G. Wierzchołki te są połączone, jeżeli odpowiednie ściany w G są sąsiednie.
- Domknięcie przechodnie grafu G Graf posiadający te same wierzchołki co G; dowolne dwa wierzchołki są w nim połączone wtedy i tylko wtedy, gdy w G istnieje między nimi droga.
w którym dwa wierzchołki są sąsiednie wtedy i tylko wtedy, gdy nie były sąsiednie w G. Inaczej mówiąc w dopełnieniu dwa wierzchołki są połączone krawędzią wtedy, gdy nie były połączone w grafie wyjściowym.
Dopisek: rysunek tłumaczy doskonale jak zrobić graf dualny do grafu planarnego, dla grafu nieplanarnego musimy znaleźć dwuwymiarową przestrzeń (osadzoną w wielowymiarze) w której ten graf jest "planarny" – na przykład K5 nie można bez przecięć narysować na kuli, ale da się na torusie i tam możemy znaleźć jego graf dualny