Problem 1:
Let G be a simple, undirected graph with an odd number of vertices. Let X be a non-empty set of all vertices with degree n(G)−1. Prove that if each component of G−X is a complete graph and if the number of odd components of G − X is less than or equal to |X|, then if we remove any vertex v of G, G − v will have a 1-factor.
Problem 2:
Let G be an undirected, simple graph with edge lengths that are positive real numbers. We would like a spanning tree of G that minimizes the maximum distance between any two leaves of the tree. Prove that we can find such a spanning tree with an algorithm whose running time is a polynomial in terms of the number of vertices and edges of G.
Problem 3:
Let G be a connected, undirected graph. We will call a graph k-resilient if we can delete any k vertices of G and for any pair of vertices that remain, there exists a simple cycle containing that pair that also avoids any deleted vertex. What is the minimum connectivity (either vertex or edge) needed for G to be k-resilient? Prove your answer correct.
Problem 4:
Let G be a bipartite graph with partition sets X and Y . Suppose that for all A ⊆ X we have |N(A)| ≥ |A|. Prove that every edge of G is part of some matching of size |X|.
Problem 5:
Let G be a plane graph. Prove that if G is isomorphic to its dual G∗ then G has 2n − 2 edges. Give an example of one such graph.
