What kind of problems do we want to solve on/via graphs?

• is the graph fully-connected?
• can we remove an edge and keep it fully-connected?
• is one vertex reachable starting from some other vertex?
• what is the cheapest cost path from v to w?
• which vertices are reachable from v? (transitive closure)
• is there a cycle that passes through all V? (tour)
• is there a tree that links all vertices? (spanning tree)
• what is the minimum spanning tree?
• can a graph be drawn in a plane with no crossing edges?
• are two graphs "equivalent"? (isomorphism)