Book: 10.1, 10.2, 10.4, 10.5. And 12.1, 12.7, 12.8 ("connected"), 12.9 ("trees"). Lectures: Monday, Thursday, week 6 (lecture notes).

Some answers are available.

The idea is that you should prepare these exercises at home, by yourself or with your group. If you have any questions, you can come to the exercise session and ask them to the assistants. (If you do not prepare in advance, there is little point in coming!)

Chapter 10: Problem 10.6 (Euler tours for directed graphs).

Now please think about these.

1. Take a look the following two directed graphs: Figure 10.3 (page 364), and the graph on page 399. Which of these has a topological ordering and which doesn't?

For the graph that has a topological ordering, construct one.

2. My friend works at a bank as an arbitrageur. He keeps track of exchange rates between currencies, and sits and makes directed graphs of the following kind all day long:

The nodes in the graph are different currencies (for example USD, EUR, SEK, etc.).

The edges in the graph point from one currency A to another currency B, if exchanging 1 unit of currency A to units of currency B would result in a profit.

Can you see why my friend becomes very excited when he discovers a cycle in one of his graphs?

(What do you think will happen once he discovers the cycle and acts on it?)

3. Take a look at the graph in the above figure. How many topological orderings are there for this graph?

4. Given a directed graph G.

Define the relation R(u,v) between nodes u and v of G as follows:

R(u,v) = "there is a directed path from u to v in G"

What properties does or doesn't R have: reflexivity, symmetry, transitivity?

5. Take a look at the following graphs: Figure 12.3 and 12.5 (page 448 in the book), and the graph on page 488. Which of these graphs have an Euler tour and which ones don't?

For the ones that have an Euler tour, construct the tour.

(picture taken from the game Dragon Age 3)

6. Take a look at the graph in the picture. Can you find an Euler walk in the graph? An Euler walk is a walk that uses every edge in the graph exactly once.

Hint: Is there an Euler tour? Why not? Can you add one more edge to the graph that would let you find an Euler tour? How does this help you find the Euler tour?

7. Given a connected ("sammanhängande") graph G.

(a.) Remove one edge from G. What are the possible different number of components the resulting graph can have? Can you give examples of each of the possibilities?

(b.) (Put back the edge you removed.) Remove one node from G, and also all edges involving that node. What are the possible different number of components the resulting graph can have? Can you give examples of each of the possibilities?

8. Given a simple graph G. Define the relation R(u,v) between nodes u and v of G as follows:

R(u,v) = "there is a path from u to v in G"

Show that R is an equivalence relation.

9 Prove: A tree with n nodes must have exactly n-1 edges.

Hint: Perform (strong) induction over the number of nodes n.

10. (*) Prove: A simple connected graph with n nodes and n-1 edges must be a tree.

(Is this still true when the graph does not have to be connected?)

Hint: You can perform (simple) induction over the number of nodes n.

The following lemma may be helpful: A simple connected graph with n>=2 nodes and n-1 edges has a leaf. A leaf is a node v with deg(v)=1, so it has exactly one edge connected to it.

11. Given a simple graph G. Show that if there exists a walk ("väg") from u till v, there also exists a path ("enkel väg") from u till v.

12. Given a simple graph G. Show that if there exists two different paths ("enkla vägar") from u till v, there is a cycle in the graph.

These exercises are for students who are looking for a challenge.

examples of tournaments with 4 nodes and with 8 nodes

1*. A tournament, also called complete oriented graph, is a directed graph that has exactly one edge between each pair of nodes, going in one direction only. (It's called a tournament because it's like letting all nodes play against each other, and draw an arrow from the winner to the loser.) See above for two examples.

A Hamiltonian path in a directed graph is a path that visits all nodes exactly once. (Contrast this with a Eulerpath that visits every edge exactly once.)

Show that any tournament has a Hamiltonian path!

Hint: Use simple induction over the number of nodes in the graph.

2*. Given a simple graph G with 6 nodes.

Show that, regardless of which edges do or do not exist, at least one of the following must always be true:

• there exist 3 nodes in G without any edges between them, OR

• there exist 3 nodes in G with edges between each of them.

Is the theorem true for graphs with 5 nodes?

Hint for the proof for 6 nodes: Pick any node, and look at whether or not there exist edges to the other 5 nodes.