Introduction to Graph Theory

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations
• Code:
  • eulerianGraph - problem statement, Java CodeExpert template & test-cases
    • Copy the contents of the Main, custom.in and custom.out files into the corresponding files of the ”Welcome” exercise. You can run the tests by using the play button (not the flask).
  • solution

Lecture Recap

This week, we introduced the notion of Graphs and proved some first properties. Notably:

Handshake Lemma

The Handshake Lemma relates the vertex degrees to the number of edges. Since by definition every edge is incident to exactly two vertices, the sum of all vertex degrees equals exactly twice the number of edges ($\sum_{v\in V​}\deg(v)=2∣E∣$).

• Corollary - In any graph $G=(V, E)$, the number of vertices with an odd degree must be even.

Cycles and Closed Walks

Often we are concerned with finding paths or exploring reachability. Two corner cases are the problems of finding closed Eulerian walks and Hamilton cycles. Although both appear like fairly simple problems, Hamilton cycles turn out to be an NP-hard problem, tough luck!

At least for Eulerian walks, there are two simple, necessary and sufficient conditions conditions that determine the existence of an Eulerian walk. We proved the following Lemma:

• Lemma: A connected graph $G=(V, E)$ has a closed Eulerian walk if and only if every vertex has even degree.

In the coding example above, you can try to implement the checks yourself!