Subgraf
Fie un graf neorientat.
Se numește subgraf al lui un graf cu proprietatea că este o submulțime nevidă a lui , iar conține toate muchiile lui care au ambele extremități în .
Spus altfel, un subgraf al unui graf neorientat conține doar o parte din nodurile grafului inițial, împreună cu toate muchiile dintre nodurilor rămase.
Exemplu de subgraf pentru un graf neorientat:
Subgraful este conex.
Observând subgraful , vedem că mulțimea de noduri este . Lipsa nodurilor , și va provoca dispariția unor muchii care altfel nu ar fi avut 2 noduri extremități.
Toate celelalte muchii ale lui , care au extremități în , vor fi păstrate în subgraf.
Numărul de subgrafuri
Numărul total de subgrafuri al unui graf neorientat este .
Formula este dedusă din faptul că fiecare nod poate fi prezent sau nu în subgraf, deci avem posibilități. Dintre acestea, trebuie eliminat cazul în care nu avem niciun nod în subgraf.