Problem 1. Show the following two properties of Minimum Spanning Trees (MST), under the assumption that no two edge weights are equal.
(a) Cut Property: the smallest edge crossing any cut must be in all MSTs. Reminder: a cut in a graph $G=(V, E)$ is a partition $A \cup B=V$.
(b) Cycle Property: The largest edge on any cycle is never in any MST.
Proof . (a) Let $G=(V, E)$ be a graph, $A \cup B=V$ a cut of this graph and let $T$ be a spanning tree of $G .$ Let $e=(u, v)$ be the edge of minimum weight that crosses from $A$ to $B$. Suppose now that $T$ does not contain $e .$ Since $T$ is connected, it contains a path $P$ between $u$ and $v,$ and $P$ must contain an edge $f$ that crosses from $A$ to $B$. But $T^{\prime}=T-f+e$ is a tree of smaller weight, which is a contradiction.
(b) Let $C$ be a cycle in $G$ and let $e=(u, v)$ be the edge of maximum weight on $C .$ Suppose it is contained in an MST $T$. Deleting $e$ from $T$ we get two connected components $T_{1}, T_{2}$. But the cycle $C$ must contain an edge $f \neq e$ with one end in $T_{1}$ and one end in $T_{2},$ and $T-e+f$ is a tree of smaller weight. Contradiction.
Problem 2. Let $G=(V, E)$ be a graph with weights $w: E \rightarrow \mathbb{R}$. Consider the problem of identifying a forest of maximum weight in $G .$ Show that this problem can be reduced to the problem of computing a minimum weight spanning tree in a suitable graph $G^{\prime}$ with weights $w^{\prime} .$ Is your reduction efficient in the sense that $G^{\prime}$ is of polynomial size in $G ?$
Proof . We construct a new graph $G^{\prime}=\left(V^{\prime}, E^{\prime}\right)$ with edge weight $w^{\prime}: E^{\prime} \rightarrow \mathbb{R}$ such that $V \subseteq V^{\prime}$ $E \subseteq E^{\prime}$ and a minimum weight spanning tree of $G^{\prime}$ restricted to $G$ is a maximum weight forest of $G .$ Let $V^{\prime}=V \cup\{u\}$ where $u$ is a new vertex and let $E^{\prime}=E \cup\{(u, v): v \in V\}$ be the new edge set. Define $w^{\prime}(e)=-w(e)$ for all edges $e \in E$ and $w^{\prime}(e)=0$ otherwise. Let $T$ be a spanning tree of $G^{\prime}$ and $F$ its restriction to $G .$ Then if $F$ is not of maximal weight, there exists an other forest $F^{\prime}$ with higher weight. Adding an edge from $u$ to each connected component of $F^{\prime}$ gives a tree in $G^{\prime}$ whose weight is lower than the weight of $T$. This implies that $T$ was not a minimal weight spanning tree and thus each minimal weight spanning tree of $G^{\prime}$ gives a maximal weight forest in $G$.
Problem 3. Use Ore’s theorem to give a short proof of the fact that any $n$ -vertex graph $G$ with more than $\left(\begin{array}{c}n-1 \\ 2\end{array}\right)+1$ has a Hamilton cycle.
Proof . Set $|V(G)|=n$. If the graph is complete then it has a Hamilton cycle. Consider two nonadjacent vertices $u, v$. Remove them to get a graph $G-u-v$ with $n-2$ vertices and $|E(G)|-d(u)-d(v)$ edges. It has at most $\left(\begin{array}{c}n-2 \\ 2\end{array}\right)$ edges, so we have
$$\begin{array}{c} \left(\begin{array}{c} n-2 \\ 2 \end{array}\right) \geq|E(G)|-d(u)-d(v)>\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1-d(u)-d(v) \\ \Longrightarrow \quad d(u)+d(v)>\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)-\left(\begin{array}{c} n-2 \\ 2 \end{array}\right)+1=n-1 \end{array}$$
Thus the condition of Exercise 2 holds, so $G$ has a Hamilton cycle.
Problem 4. We say that a vertex $u$ in a tournament is almost central if for every other vertex $v$, there is a directed $u-v$ path of length at most
2. Prove that every tournament has an almost central vertex.

Proof .

Solution: We proceed by induction on the number of vertices. For $n=2,$ it is clear. Let $n>2$ and let $G=(V, A)$ be a tournament on $n$ vertices. Pick a vertex $w$ and consider the tournament $G^{\prime}=G-w$ on the set $V^{\prime}$ of $n-1$ vertices. By induction, there exists an almost central vertex $v$ in $G^{\prime}$. The situation now breaks down in three cases. If there is an arc $a \in A$ directed from $v$ to $w,$ then $v$ is almost central in $G .$ Otherwise, consider the sets $V_{i}^{\prime}:=\left\{u \in V^{\prime} \mid d(v, u)=i\right\}, i=1,2,$ of vertices at distance $i$ of $v .$ Note that because $v$ is almost central in $G^{\prime}$, we have that $\{v\} \cup V_{1}^{\prime} \cup V_{2}^{\prime}=V^{\prime}$. If there is an arc directed from $V_{1}^{\prime}$ to $w,$ the $v$ is almost central in $G .$ Otherwise, all arcs between $w$ and $V_{1}^{\prime}$ are directed from $w$ to $V_{1}^{\prime}$ and there is a directed path of length at most 2 from $w$ to all vertices in $V_{1}^{\prime} \cup V_{2}^{\prime} .$ Furthermore, $w$ and $v$ are connected by an arc from $w$ to $v$. Thus $w$ is almost central in $G$.