Exploring critical network points (articulation points, bridges), pathfinding challenges (Eulerian/Hamiltonian paths), and network flow problems.
Identifying critical vertices and edges whose removal would disconnect a graph.
Finding paths that visit every edge (Eulerian) or every vertex (Hamiltonian) exactly once.
Finding the maximum rate at which a material can flow through a network from a source to a sink.