Exercise 1693Combinatorics › Graph theoryM1Added 3 Nov 2026
NP-hard problems in graphs
#NP-hard#Hamiltonian#coloring
Statement
State which classical graph problems are polynomial and which are NP-hard.
Hint
Spanning tree, shortest paths are polynomial; Hamiltonian cycle, 3-coloring are NP-hard.
Show solutionHide solution
Solution
Polynomial.
- Spanning tree (Kruskal, Prim).
- Shortest paths (Dijkstra, Bellman-Ford).
- Matching (Hopcroft–Karp for bipartite).
- Planarity testing (Hopcroft–Tarjan).
NP-hard.
- Hamiltonian cycle.
- Chromatic number (even 3-colorability).
- Clique number.
- Traveling salesman.
Conclusion. Computational complexity of graph problems is a vast area of research.