Graph Theory Problems: Assignment

Answered

Problem 1

Let G be the graph of vertices 1, 2, 3, 4 and edges 12, 13, 14, 23, 24, 34. Can it be drawn starting from some vertex but without ever lifting the pen from the paper?

Problem 2

Let G be an acyclic graph with n vertices and exactly k connected components. Show that G has n − k edges.

Problem 3

[Planarity] Draw an example of a graph that is

•planar and 2-connected

•planar, but not 2-connected

•2-connected, but not planar

•(bonus points) neither planar, nor 2-connected.

Problem 4

Let G be a k-connected graph with n vertices. Prove that between any two non-adjacent vertices a and b of G, there is a path consisting of not more than n−2 + 1 edges.

Problem 5

Find the maximum flow value in the following (s, t)-network, where the edge capacities have been marked in black.

Bonus points: (1) Indicate the cut of minimum capacity. (2) Explain why it’s not a surprise that the maximum flow is integral, even if not all capacities are integers.