Problem 16
Assume that all the weights on the edges of a graph are positive. Prove that if no two edges in a graph have the same weight, then the MCST is unique. (Hint: Assume \(G\) has more than one minimal spanning tree, Order the edges, and consider the smallest subscript \(k\) of an edge that belongs to some, but not all, minimal spanning trees.)
Problem 17
Let \(D=(V, E)\) be a tournament. Prove that if \(a\) has maximum score, then for any vertex \(y,\) either there is an edge \((a, y)\) or a vertex \(w\) and edges \((a, w)\) and \((w, y)\).
Problem 17
Let \(G=(V, E)\) be a graph. Prove that if \(|E|<|V|-1\), then \(G\) is disconnected.
Problem 17
Find an algorithm for determining an MCST that is based on removing the maximum cost edge from a cycle at each step.
Problem 18
Let \(F: T \rightarrow S\) be an isomorphism between binary trees \(T\) and \(S\). Let \(v \in T\) be a vertex at level \(k\) for \(k \geq 0\). Prove that \(F(v)\) is at level \(k\) in \(S\).
Problem 18
Find connected graphs with at least eight vertices such that: (a) \(G\) is Eulerian and not Hamiltonian. (b) \(G\) is not Eulerian but is Hamiltonian. (c) \(G\) is not Eulerian and not Hamiltonian. (d) \(G\) is Eulerian and Hamiltonian.
Problem 18
Prove that a tournament with no cycles is transitive.
Problem 18
Prove that if a graph \(G\) has an \(n\) -circuit with \(n\) odd and \(n>3\), then \(G\) has an odd cycle.
Problem 19
Prove that if \(D\) is a tournament, then it has a directed Hamiltonian path.
Problem 19
Show that 1,2,2,3,4 is graphical but that 1,3,3,3 is not. Prove the theorem of Havel-Hakimi that for \(n \geq 1,\) the sequence \(d_{1}, d_{2}, \ldots, d_{n}\) is graphical if and only if \(d_{1}, d_{2} \ldots \ldots d_{n-d_{n}}, d_{n-d_{n}+1}-1, \ldots, d_{n-1}-1\) is graphical.
