Wednesday 13/10 - EXERCISES W7 - Graphs - ANSWERS

Preparation

Lectures: Thursday, Friday, week 6.

Read: Book 10.1, 10.2, 10.4, 10.5. And 12.1, 12.7, 12.8 ("connected"), 12.9 ("trees"). Notes on graphs in general (pdf), Notes on topological sorting (pdf).

Basic Exercises

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

Exercises

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

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

(2.) Given a directed ("riktad") graph G with n nodes and n+1 edges (arrows).

Check whether or not these statements are true or false, and give an argument why.

(a) G must have a cycle.

(b) G must have at least one node with indegree 2.

(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 466 in the book), and the graph on page 485. Which of these graphs have an Euler tour and which ones don't?

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

(6.) This image makes the rounds on Facebook and Twitter every now and then. Is there a solution? Why/why not?

If there is no solution, what single door can we close such that there exists a solution?

Hint: Model the house as a graph. Look at the even/oddness of the degrees of the nodes in your graph. The riddle does not ask for an Euler tour, but an Euler walk - start and finish do not have to be at the same point. How many nodes with odd degree are allowed if start and finish do not have to be the same node?

(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.) 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.

Starred Exercises

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

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

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.

Follow-up question: Are all graphs with n nodes and n-1 edges connected?

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

Start by drawing a few graphs with 6 nodes and check that the theorem is actually true.

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.