This is probably not what you're looking for, but if I were teaching such a course I'd focus on the interplay between algorithms for various graph problems and the more traditional mathematical approach of proving theorems in graph theory.
For example, you can prove the "max flow-min cut" theorem by developing an algorithm that simultaneously finds a maximum flow and a corresponding min-cut.
