Reference no: EM132678882

Problem 1. Let G be a graph. Prove or disprove each of the following statements.

(i) If G has no bridges, then G has exactly one cycle.

(ii) If G has no cutvertices, then G has no bridges. (iii)If G has no bridges, then G has no cutvertices.

[Hint/Clarification. Given any one of the above statements, if (you believe) it is correct, you will have to verify it for an arbitrary graph G (and not only for a specific graph of your choice). On the other hand, if (you believe) it is false, then you only need to give one example of a graph G that fails to satisfy the statement; it may help in such a case to look at examples of graphs we have seen in class (or of subgraphs of such graphs).]

Problem 2. Let G be a connected graph of order n. We have seen in Whitney's theorem that we always have
κ(G) ≤ δ(G).
Show that, if δ(G) ≥ n - 2, then we have κ(G) = δ(G).
[Hint/Clarification. Here you need to consider an arbitrary connected graph G which satisfies δ(G) ≥ n - 2 (that is, these are the only properties you can be sure your graph has, and you can't assume anything else particular about your graph); moreover, you can't just consider a specific graph of your choice which has these properties and verify the conclusion just for that one graph. Still it may help to consider some examples first, if you can't come up with a general approach right away.

Note also that, for instance, one of the inequalities which the problem asks you to disprove is the inequality κ(G) < n - 2 ≤ δ(G); why would this always fail?]

Problem 3. Let K be a connected graph. Prove or disprove the following statement: if K is not a tree, then K has at least two spanning trees.

Problem 4. Consider the following two graphs. For each one of them, determine δ(G), κ(G) and λ(G) precisely (you may use any of the methods we have discussed, or a combination of them).

Problem 5. (a) For each of the graphs in Problem 4 above, find two spanning trees: more specifically, consider a labelling of the vertices of the graph, and use this labelling to describe in (V, E)-notation the two spanning trees you will find (in addition, you may draw the trees if you want).

(b) Below is graph G2 from Problem 4 again, with its edges coloured in different ways to indicate that each of them has some weight.

Assume that
• the weight of eachlight pinkedge is 10;
• the weight of eachgreenedge is 25;
• the weight of eachturquoiseedge is 35;
• the weight of eachpurple / bright pinkedge is 40;
• and the weight of eachrededge is 55.

Find a minimum weight spanning tree of G2, and determine its total weight. Show all your work.

Attachment:- HW3F20.rar