Alexander Schrijver, A Course in Combinatorial Optimization includes multiple applications (just search for "Application" in the text). The parts that appear to get used the most are shortest paths, maximum flows, maximum matchings and arc-disjoint paths. Of course, it is usually the algorithms that get applied rather than the existence theorems, but this is common to almost all applications of mathematics, and most of the theorems have algorithmic proofs (which, in some cases, are the standard proofs).
Alexander Schrijver, On the history of the transportation and maximum flow problems focusses on the history of the maximum-flow/minimum-cut theorem. I won't spoil the punchline, but let me just mention that both the maximum-flow and the minimum-cut problem appeared in the middle of the 20th century out of non-mathematical considerations, and both were intended to be applied to the same network.
I generally have the impression is that you don't often see "mere" graphs in the applied world (i.e., graphs with no extra structure on the vertices and edges), because there is usually more information available and it is stupid to ignore it. So you will often see networks, matrices and various other models instead. Note that what is commonly called a "sparse matrix" is essentially a graph with numbers on its edges; so every sparse matrix algorithm that is used in the real world is an application of graph theory.