Problem 4. (5 marks) Let G = (V, E) be a connected graph, let T be a spanning tree of G, and let e ∈ E\E(T). Prove that there is an edge f ∈ E(T) such that  = (V, (E(T)\{f}) U {e}) is also a spanning tree of G.

Solution:  Consider the graph H  =  (V, E(T) U {e}).  Notice that H has  IV I edges.  By a result from class, H is not a tree and therefore H contains a cycle C.  Since C has at least three edges, C has an edge f such that f  e.  Since f  e, we see that f ∈ E(T). Furthermore, since f is contained in a cycle, f is not a bridge of H . Therefore,  = H\f = (V, (E(T)\{f}) U {e}) is connected with IV I 一 1 edges. This means that  is a spanning tree of G, as required.

Problem 5.  (6 marks) Let G be a connected graph such that each vertex x has a weight w(x) ∈ R, such that if vertices x and y have a common neighbour, then w(x) = w(y).

(a)  Show that there are at most two different weights (Hint: Start with a walk that visits

every vertex).

Solution:  Since G is connected, G has a walk that visits every vertex.  Let W  = v0 , v1 , v2 , . . . , vk  be such a walk.  Notice that all the vertices with an even index have the same weight and all the vertices with an odd index have the same weight.  Thus there are at most two weights (If a vertex appears twice in the walk with both even and odd indices, then there is only one weight).

(b) Which graphs have such a weighting?

Solution: This was supposed to say “Which graphs have such a weighting with exactly two weights”, for which the answer is the class of bipartite graphs. However, since this part was not asked properly, everyone will get the marks for it.

Problem 6. (9 marks) Use Prim’s algorithm to find a minimum weight spanning tree of the following weighted graph.  Start with root b.  List the edges added to the tree in the order they are added and the final weight of the tree.

e

b