- isomorfismo
- caminho mínimo
- circuito máximo (e circuito hamiltoniano)
- decomposição em circuitos e cobertura por circuitos
- conjunto estável máximo
- emparelhamento máximo
- coloração mínima de vértices
- coloração mínima de arestas
- coleções disjunta máximo de caminhos (fluxo máximo)
- planaridade
Mas a teoria dos grafos não se limita a problemas computacionais. Uma importante parte da teoria que trata das relações entre vários parâmetros de um grafo: a relação entre o número cromático e o gênus do grafo, por exemplo.
Outra parte importante da teoria trata de grafos aleatórios e da evolução de seus parâmetros (como o número cromático, por exemplo) em função do número de vértices.