There exist many more interesting and useful areas studied by graph theory than those notoriously known topics (at least in CS) of the first four lectures. We offer a representative selection of those areas that should be in the curriculum of every general course on graph theory, in the next four lectures. Instead of focusing on "easy" algorithms, we are now going to look onto graph problems, most of which are inherently hard.

The main reason (besides nice pure mathematics) why to look at these more difficult topics of graph theory is to give CS students good overview and "feeling" of what advanced tools they can use in solving the many real-world problems based on graphs, and what can and cannot be solved efficiently. To achieve this goal, we also include a brief survey on computational complexity hardness of many graph problems at the end.