1-
How many weighings of a balanced scale are needed to find a counterfeit coin
among eight coins if the counterfeit coin is either heavier or lighter than the
others? Describe your method. (Hint: Correct representation will bring you very
close to the solution).
2-
Let T1 and T2 and T3 be spanning trees of a simple graph G. The distance between Ti and Tj
is the number of edges that are in exactly one of them. Show that the
distance between T1 and T3 does not exceed the sum of
the distance between T1 and
T2 and the distance between T2 and T3.
3-
Show that if no two edges in a weighted graph have the same weight, then the
edge with the least weight incident to a vertex v is included in every minimal spanning tree.
Deadline: