Book: 7.1-7.4. Lectures: Thursday, Friday, 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!)

Make sure you are comfortable with the following before you start the next exercises:

Chapter 7: 7.1(a-d), 7.3, 7.4.

Now please think about these.

1. Take a look at Figure 7.3 in the book (page 192), where you can see 5 examples of graphs. Which of these graphs have an Eulercycle and which ones don't?

For the ones that have an Eulercycle, construct the cycle.

(picture taken from the game Dragon Age 3)

2. Take a look at the graph in the picture. Can you find an Eulerpath in the graph? An Eulerpath is a path that uses every edge in the graph exactly once.

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

3. 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?

4. 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.

5. Prove lemma 7.7 from the book (page 194): A tree with n nodes has exactly n-1 edges.

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

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

8. Take a look at Fig. 7.8 and 7.9 from the book (page 200-201), where you can see two examples of directed graphs. Which of these has a topological ordering and which doesn't?

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

9. 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?)

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

11. 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?

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.