Exam 2 sample problems


Be sure to justify your answers.

1.
The graphs on the top row are both the petersen graph. Instead of using pure brute force to find a isomorphism, try mapping a feature in one graph to the same feature in another. For example we knew we needed to find the outer 5-cycle in the graph on the left, so we started labeling the cycle 1,2,3,4,5 and worked from there.

Although the number of vertices, edges, and the degrees match, the third graph has a hamiltonian cycle, a cycle that visits each vertex in V exactly once, while the petersen graph does not have a hamiltonian cycle.

2.
The edge chromatic number of the petersen graph is 4. The only way to color the outer 5-cycle is by 2 edges of one color, 2 edges of another color, and an edge of a third color. The colors of the remainder of the edges are determined once we do this.

The brown vertices consist of an independent set of size 4, which can be verified as the maximum by showing that any set of 5 vertices contains an edge.

3.
The graph on the left above is planar, while you can contract two edges of the graph on the right to make it look like K_{3,3}, which means that if one could embed it in the plane, one could embed K_{3,3} in the plane, which is impossible.

4. Prove that a tree T contains at most one perfect matching. How many perfect matchings does a cycle on n vertices contain?

We'll simply show that we don't have any choices to make, so that if there is a perfect matching, it's determined by the tree. Consider some leaf u. It must be matched with its parent, v. Vertex v might be adjacent to some other leaves, in which case there is no perfect matching. If not then remove the edge uv (since it must be in a perfect matching) and continue. We know that since the graph is acyclic, we'll always have a leaf. We continue the procedure until we end up with a perfect matching, or along the way find there isn't one. Since we never made any choices (every leaf must matched to its parent), there is at most one perfect matching.

5. Prove that a tree T contains a unique {u,v}-path for every pair of vertices u,v in V(T).

We'll prove it by contrapositive: Suppose there is more than one {u,v}-path for some pair u,v. This means there's a closed walk containing u and v; but every closed walk must contain a cycle, so the graph couldn't have been a tree. So this means that if the graph is a tree then it can't have more than one {u,v}-path for every pair u and v in V(T).

6. Show that a graph G is bipartite if and only if every induced subgraph H of G contains an independent set of size at least |V(H)|/2.

First we show that if G is bipartite then the condition on H holds. Let A and B be the sets of the bipartition of G. Every induced subgraph H must contain k vertices from A and |V(H)|-k vertices from B for some k. since k + (|V(H)|-k) = |V(H)|, at least one of the two has to be at least |V(H)|/2, so we simply take all the vertices from the corresponding side since we know A and B are each independent sets.

Now we show that if the condition on H holds, our graph must be bipartite. Suppose the condition holds. We'll show by contrapositive that we can't have any odd cycles in this case. Suppose we have some odd cycle. Then we must also have some minimal odd cycle C (one that doesn't contain any chords). Let H be the induced subgraph on the vertices of C. But an independent set in an odd cycle can't be larger than (|V(C)|-1)/2 = (|V(H)|-1)/2 < |V(H)|/2, so we've violated our condition. This tells us that if our condition holds we can't have any odd cycles, hence our graph must be bipartite.

7. Show that a connected graph G with exactly |V| edges has exactly one cycle.

Since our graph is connected it must have a spanning tree T, which has |V|-1 edges. Since G has |V| edges, it is simply T plus some edge uv. By 5. above we know that T contains a unique {u,v}-path, hence adding uv creates exactly one cycle.