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 G−e 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 ui to leaf vi. Consider two leaves a and b of T different from {u1,...,uk,v1,...,vk}, and consider the path from a to b in T. Suppose that the intersection of this a–b 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,u1,...,uk,v1,...,vk}.
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 G−xy 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:
u1
u2
w
v1
v2
@ 1 @
@ @ @ @ @ @
@ @
@ @
@w @
2
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 Erd¨os-R´enyi random graph G(n,1/2).
