Description
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:
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.
Problem 10:
Let α be the following shape.
✒✑
✓✏u2
✒✑
✓✏u1
✒✑
✓✏w2
✒✑
✓✏w1
✒✑
✓✏v2
✒✑
✓✏v1
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
Describe entries of the matrix Mα representing this shape on a Erd¨os-R´enyi random gra
