Homework 1

att lämnas in fre 26/4

The following exercises are of varying degrees of difficulty, though I won’t spoil your fun (!) by telling you which I think are easier. I don’t expect people to solve all the exercises - indeed solving fully about 5 of them is definitely godkännt. Consider the rest as study material.

Unless otherwise stated, all graphs G are simple and undirected.

Q.1 Show that it is always possible to order the vertices of a graph G in such a way that the greedy algorithm provides a coloring of G using exactly χ(G) colors.

Q.2 (i) Show by means of an example that Mantel’s theorm is ‘bestpossible’, i.e.: for each n > 0 give an example of a graph on n vertices with ⌊n^{2}/4⌋ edges and no 3-cycles. (ii) Prove Mantel’s theorm by induction - exercise 8.8.2.

Q.3 Consider the following version of a lottery : you pick 5 numbers from 100. Then 10 numbers are drawn and you win if your 5 are among these. The question now is : how many lottery cards do you need to buy in order to be certain of winning ?

Can you formulate a generalisation of Turán’s theorem which would include this question ? If you can answer the question, that would be highly impressive, since I’m pretty sure the answer isn’t known (I am definite that no general methodis known for answering this type of question).

Q.4 Let T be a tree. Show that T has at least 2 nodes of degree 1 (exercise 8.5.2). Note : such vertices are called leaves.

Q.5 (i) Find all non-isomorphic trees T on 7 vertices. (ii) Pick any two of your trees and compute the number of different ways to color each tree with exactly 2 colors. Notice anything ?

Q.6 Exercise 8.8.7.

Q.7 (i) How many Hamilton cycles does K_{n} have ?

(ii) Exercise 8.8.13. (iii) How many Euler cycles do K_{6} and K_{7} have ?

Q.8 Find the chromatic number of the underlying graph of Figure 9.8.

Q.9 (i) Show, by means of an example, that the claim of exercise 8.8.22 is false ! (ii) On the other hand prove that, for any graph G on n vertices,

χ(G) + χ(\overline{G}) ≤ n + 1.

Q.10 (i) Exercise 8.8.14. What about n × n chessboards for general n ? (ii) Does the graph of this exercise have any Euler cycles ?

Q.11 (i) Draw any 3 connected, planar graphs having, rsspectively, 6.10 and 15 vertices. For each graph compute |V (G)|, |E(G)| and |R(G)| where |R(G)| is the number of enclosed regions of G. Then compute, for each graph,

|V (G)| − |E(G)| + |R(G)|.

Notice anything ? Can you formulate and/or prove a theorem ? (ii) Repeat the above procedure with a football !!

Q.12 Let G be the undirected graph got by removing the arrows from the graph on p.263. For this graph

(i) Use DFS to find a spanning tree in which the first edge chosen is {s, a}. (ii) Use DFS to find a min. weight spanning tree. (iii) Use BFS to find a shortest path from s to t.

N.B.: Show all your calculations in each part !

Q.13 Show that it is not possible for both G and \overline{G} to be disconnected.

Q.14 Exercises 8.8.18 and 8.8.19.