Graph Theory

References

Cite

Share

Abstract

You are encouraged to work together on solving homework problems, but please put their names clearly at the top of the assignment. Everyone must turn in their own independently written solutions. Homework is due at the beginning of class. def = {0, 1} 2012 , the set of all binary strings of length 2012, in which two vertices are connected if and only if they differ in precisely 1006 coordinates. Prove that G has a perfect matching. 2. Prove that any simple graph G on 2n vertices with δ(G) ≥ n + 10 has at least 12 edge-disjoint perfect matchings. 3. Describe all simple connected graphs for which their line graph is: (a) complete; (b) bipartite.