Tutorial 6

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 graph and $E$ its edge incidence matrix.
Give KCL and KVL interpretations to the equations $xE=0$ and
$Ey=0$.

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.

7. Let $M$ and $M'$ be two complete matchings in a bipartite
graph. Show that $M exor M'$ is collection of disjoint
alternating cycles. 

8. Let $G$ be a bipartite graph with costs on edges. The cost of a
matching is defined to be the sum of the costs of the edges
comprising the matching. Show that if $M$ is a complete matching
NOT of minimum cost, then there is an alternating cycle such that
the sum of costs of matched edges exceeds the sum of costs of
unmatched edges in the cycle.