- Answers to Exercises 275
connected, it has an edgefconnecting these two components. The edgef
cannot be more expensive thane, or else the pessimistic government would
have chosenfto eliminate instead ofe. But then we can replaceebyf
inHwithout increasing its cost. Hence we conclude as in the proof given
above.
9.1.2. Take nodes 1, 2 , 3 ,4 and costsc(12) =c(23) =c(34) =c(41) = 3,
c(13) = 4,c(24) = 1. The pessimistic government builds (12341), while the
best solution is 12431.
9.2 Traveling Salesman
9.2.1. No, because it intersects itself (see next exercise).
9.2.2. Replacing two intersecting edges by two other edges pairing up the
same 4 nodes, just differently, gives a shorter tour by the triangle inequality.
10 Matchings in graphs
10.1 A Dancing Problem
10.1.1. If every degree isd, then the number of edges isd·|A|, but also
d·|B|.
10.1.2. (a) a triangle; (b) a star.
10.1.3. A graph in which every node has degree 2 is the union of disjoint
cycles. If the graph is bipartite, these cycles have even length.
10.3 The Main Theorem
10.3.1. LetX⊆Aand letYdenote the set of neighbors ofXinB. There
are exactlyd|X|edges starting fromX. Every node inY accommodates
no more thandof these; hence|Y|≥|X|.
10.3.2. The assumption forX=Ayields that|B|≥|A|.If|B|=|A|, then
we already know the assertion (Theorem 10.3.1), so suppose that|B|>|A|.
Add|B|−|A|new nodes toAto get a setA′with|A′|=|B|. Connect every
new node to every node inB. The graph we get satisfies the conditions
in the Marriage Theorem (Theorem 10.3.1): We have|A′|=|B|, and if
X⊆A′then eitherX⊆A(in which case it has at least|X|neighbors in
Bby the assumption of the exercise), orXcontains a new node, in which
case every node inBis a neighbor ofX. So the new graph has a perfect
matching. Deleting the newly added nodes, we see that the edges of the
perfect matching that remain match all nodes ofAwith different nodes of
B.