[Solved] CSDS455 Final Exam -Applied Graph Theory

Problem 1:

Prove that G = H if and only if G = H.

Problem 2:

Prove that every regular bipartite graph has a perfect matching.

Problem 3:

Let G be a k-connected graph that is not a complete graph. Prove that for every edge e of G, if the result of contracting that edge is a graph that is no longer k-connected, then Ge is a k-connected graph.

Problem 4:

Let T be a tree (undirected). Suppose we have k vertex disjoint paths in T such that path i goes from leaf u_i to leaf v_i. Consider two leaves a and b of T different from {u₁,,u_k,v₁,,v_k}, and consider the path from a to b in T. Suppose that the intersection of this ab path with path i, for each i, is either or contains at least two different vertices. Prove that there exists k + 1 vertex disjoint paths in T between the leaves {a,b,u₁,,u_k,v₁,,v_k}.

Problem 5:

Let G be a simple plane graph in which all vertices have a degree that is a prime number (2,3,5,7,). Furthermore, assume that G requires 4 colors to properly color its vertices but any subgraph of G requires only three colors. Prove that G must have either a vertex of degree 3 on a face of size 5 or less or a vertex of degree 5 incident to 4 faces of size 3.

Problem 6:

Let graph G require (G) + 1 colors to properly color its edges. Assume G is critical for this coloring. Prove that G is bridgeless.

Problem 7:

Let G be a directed graph, let xy be an edge and assume Gxy is bridgeless. Prove that if G has a nowhere-zero 2-flow then G xy has a nowhere-zero 3-flow.

Problem 8:

Prove that having treewidth at most k is a hereditary property.

Problem 9:

We know that if each graph in a set of graphs has treewidth at most k, for some constant k, then we can solve problems such as Hamiltonian cycle, graph isomorphism, vertex cover, and 3-color on these graphs using dynamic programming where the running time of the algorithm is a polynomial on the size the graph. Explain why dynamic programming is able to solve these problems and can work in polynomial time. Let be the following shape. Problem 10:

Describe entries of the matrix M representing this shape on a Erdos-Renyi random graph G(n,1/2).