[Solved] CSDS455 Midterm

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 GX 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.