3
$\begingroup$

Please could I ask for some help with this exam past paper question:

A connected graph G has five vertices and has eight edges with lengths 8, 10, 10,

11, 13, 17, 17 and 18.

(a) Find the minimum length of a minimum spanning tree for G. (2 marks)

(b) Find the maximum length of a minimum spanning tree for G. (2 marks)

(c) Draw a sketch to show a possible graph G when the length of the minimum spanning tree is 53. (3 marks)

ANSWER:-

6(a) Min MST = 8 + 10 +10 + 11 = 39

(b) Max MST = 8 + 17 +17 +18 = 60 Alternatively: 8 + 18 + 2 others = 60

I found this question discussed here and some people think there is an error in the question.

I'm not sure, the answer to (a) seems reasonable. For (b) the answer states the solution must include 8. I found this entry on wikipedia :

If the edge of a graph with the minimum cost e is unique, then this edge is included in any MST.

Proof: if e was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight.

In this example 8 is the minimum cost edge, so I based on this result in must be in any MST.

Does anyone know if this is a well-known result (perhaps with a name?) it is supplied without a reference on wikipedia. Thanks, C

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ The logic seems to be that adding this edge with (minimum) cost $e$ to a minimum spanning tree will create a cycle. One then needs to argue that some other edge in the cycle, with cost above $e$, can be removed to again have a cycle-free connected subgraph, i.e. a spanning tree. Are you looking for a reference or lemma-identification of a more formal nature? $\endgroup$ – hardmath Jun 21 '15 at 21:11
  • $\begingroup$ "M" in MST on that page is minimum, and (b) is asking about a maximum. $\endgroup$ – user208649 Jun 21 '15 at 22:13
  • 1
    $\begingroup$ @CuddlyCuttlefish It's a bit of an odd question. It's asking for the "maximum minimum spanning tree". The way I read this question is this - the number of vertices and number and length of edges is specified, but this does not uniquely define a graph. But it does restrict you to a set of possible graphs which meet these criteria, each graph will have an MST, the question (I think) asks of all the graphs in this set which has the "maximum" MST. $\endgroup$ – clumb Jun 22 '15 at 11:59
  • $\begingroup$ @hardmath - I looking into this for a friend and I just wanted to get some verification of this result before I went back and said "it's because of this..." with it being wikipedia I really was looking for a second source or a someone who knows about graph theory saying "yes, this is a valid result". Thank you for looking at this. $\endgroup$ – clumb Jun 22 '15 at 12:03
  • $\begingroup$ Ahhh - in that case, it is true that it must have the edge with weight $8$. $\endgroup$ – user208649 Jun 22 '15 at 18:27
2
$\begingroup$

Part $(b)$ is only true if we assume that $G$ has multiple edges but no loops.

The Wikipedia page is a little misleading; it might be more accurate to say that at least one of the lowest weight edges will be in a minimum spanning tree (in a loopless graph).

This is apparent from the application of Kruskal's Algorithm for constructing a minimum spanning tree. Essentially, select the lowest weight vertex at each step that will not introduce a cycle. Because it is impossible to create a cycle when selecting the first edge in a loopless graph (per assumption) Kruskal's Algorithm will always select it.

In order to rule out the length $10$,$10$, $11$, and $13$ edges, they must all create cycles if they are included with the $8$ edge; this implies that there is a multiple edge with $8$,$10$,$10$,$11$, and $13$ all connecting the same two vertices.

I would say it's very non-standard to allow multiple-edges but not loops in the graph, because problems are generally a matter of simple vs. non-simple, where loops are allowed in non-simple graphs. Clearly, you can obtain a higher result by making $8$,$10$,$10$, and $11$ edges all loops, while using the other $4$ to create the spanning tree.

I would ask your professor to clarify this point, and definitely ask during an exam if a question is vague.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It's quite normal to allow multiple edges but not loops in a lot of these applications, since you can have multiple routes between two towns, or multiple resistors connected in parallel, etc., but loops don't naturally arise. The terminology has never really been standardised, but it's not uncommon to make the distinction between "multigraphs" and "pseudographs" (where the former doesn't allow loops): see en.wikipedia.org/wiki/Multigraph $\endgroup$ – Especially Lime Oct 10 '19 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.