Tutorial 5
1. Let $G$ be a connected graph and $S$ and $T$ be two spanning
trees. Let $e\in S$ be a tree-edge for $S$. Show that there is an
edge $f\in T$, such that $S-e+f$ and $T-f+e $ are spanning trees.
2. Let $G$ be a connected graph such that all vertices have even
degrees. Show that there is a cycle (duplicate vertices allowed)
which travels every edge in the graph exactly once. Such a cycle
is called an eulerian trail.
3. Show that for a flow in a network, the amount by which conservation
(KCL) fails at the source $s$ is the negative of the amount at the
sink $t$.
4. Show that the value of a flow is always dominated by the value
of any cut.
5. Compute the number of spanning trees for the complete graph on
$n=4$ vertices, i.e., where all pairs are connected by edges. Draw
these trees. Compute, just the number, for $n=5$.
6. Show, using 1 or otherwise, that if the edge costs are
distinct then the minimum cost spanning tree is unique.