Math 581: Topics in Graph Theory
Fall 2010

Matching Theory
Additional Exercises

To the main course page.

1. (See Erratum No. 1.) Write an algorithm to find the initial forest needed in the Hungarian algorithm.
   
   
2. (See Erratum No. 2.) Use the information available in the book (see p. 32) to decide what the correct definition of a forest-representative system is.
   
   
3. (See Erratum No. 3.) Is this really an error in the book or is my brain deceiving me?
   
   
4. Write a complete and correct proof of Lemmas 2.2.5 and 2.2.6 using the method I tried in class, where we adjust the paths to show that P_i+1 is not shorter than P_i and that |P_i+1| ≥ |P_i| + 2 if a "saturated edge" of the flow f_i is in P_i+1 . Do not use the method in the book, but you may use it as a source of ideas.
   
   Another (related) thing to consider: Is it simpler to combine the two lemmas' proofs?
   
   
5. A thought question: In f-matchings, why is f allowed to take on real values instead of only integer values?
   
   
6. Prove sufficiency in Theorem 3.2.8.
   
   
7. Prove necessity in Theorem 3.2.8.
   
   
8. Prove that every barrier is extreme.
   
   
9. Use Lemma 4.2.9 to prove the assertion of page 134, paragraph 3.
   
   
10. Is there a converse of Theorem 5.2.2(c)? Precisely stated: Suppose X is a nonempty subset of V such that A(G - S) = S_i - X for some maximal barrier S_i, and also C(G - X) is empty. Is X nececessarily contained in S_i?
    
    
11. In the ear decomposition of a 1-extendable graph (Section 5.4), can you figure out why it may be necessary to add 2 ears at the same time, but never 3? (That is, any graded ear decomposition can be refined to one with no stage larger than a 2-ear system.) In particular, does this have anything to do with the fact that the matching polytope is half-integral? Or that a signed-affinographic, integral hyperplane arrangement has half-integral vertices?
    This is a serious research problem, not an exercise.
    
    
12. State each of the following, completely and correctly, as appropriate to each case. Do not waste words.
    1. Theorem 3.1.1:
       1. The sufficiency half.
       2. The necessity half.
    2. Theorem 3.1.3:
       1. The sufficiency half.
       2. The necessity half.
    3. Theorem 3.2.8:
       1. The sufficiency half.
       2. The necessity half.
    4. Theorem 3.4.7:
       1. The sufficiency half.
       2. The necessity half.
    5. Theorem 4.1.1:
       1. The sufficiency half.
       2. The necessity half.
    6. Theorem 4.1.6:
       1. The sufficiency half.
       2. The necessity half.
    7. Theorem 5.1.3:
       1. The sufficiency half.
       2. The necessity half.
    8. Theorem 5.2.7:
       1. The sufficiency half.
       2. The necessity half.
    
    
    

To the main course page.
To my home page.