4. The "house graph is an undirected graph with five vertices a, b, c, d, and e, and six edges a-b, b-c, c-d, a-d, a-e, and d-e. It is called that because it can be drawn with abcd as a square and ade as a triangle on top, resembling a child's drawing of a house. (a) How many spanning trees does this graph have? (It may help to observe that the house graph has three paths from a to d, that each spanning tree must include one of these paths, and that one edge must be removed from each of the other two paths. How many ways are there of doing this?) (b) If we choose random weights for the edges (independently, but with no two weights equal) then every sorted order of the weights, as used in Kruskal's algorithm, will be equally likely. How many different sorted orders are possible? (c) Combine your answers from (a) and (b) to show that if we choose random weights for the house graph and then find a spanning tree, some trees will be more likely to be generated than others. You do not have to calculate the probabilities of generating each tree. (Hint: if your answer to (b) is 2, then each tree will have a probability that is an integer multiple of 1/x.) 4. The "house graph is an undirected graph with five vertices a, b, c, d, and e, and six edges a-b, b-c, c-d, a-d, a-e, and d-e. It is called that because it can be drawn with abcd as a square and ade as a triangle on top, resembling a child's drawing of a house. (a) How many spanning trees does this graph have? (It may help to observe that the house graph has three paths from a to d, that each spanning tree must include one of these paths, and that one edge must be removed from each of the other two paths. How many ways are there of doing this?) (b) If we choose random weights for the edges (independently, but with no two weights equal) then every sorted order of the weights, as used in Kruskal's algorithm, will be equally likely. How many different sorted orders are possible? (c) Combine your answers from (a) and (b) to show that if we choose random weights for the house graph and then find a spanning tree, some trees will be more likely to be generated than others. You do not have to calculate the probabilities of generating each tree. (Hint: if your answer to (b) is 2, then each tree will have a probability that is an integer multiple of 1/x.)