Practice Second Test

Mathematics 61, section 1

Disclaimer: Listed here is a selection of the many possible sorts of problems. The actual test is apt to make a different selection.

1. (a) Assume that T is a tree with 10 vertices. We want to know about the average of the degrees of the vertices. How small can that be? How large can it be?
(b) Assume that G is a planar graph with 2 components, 9 faces, and 10 vertices. Again we want to know about the average of the degrees of the vertices. How small can that be? How large can it be?

2. Let G be the weighted graph given in Exercise 4 of the section Minimal Spanning Trees. Suppose we apply Dijkstra's algorithm to find a shortest path from 1 to 12. List the explored (circled) vertices, in the order in which the algorithm adds them. (The reason for giving this list is to show that you are in fact using Dijkstra's polynomial-time algorithm, and not merely using exhaustive search, which is not polynomial-time.)

3. (a) What is the least number of edges we can add to K_4 to obtain a graph (not necessarily a simple graph) with an Euler cycle? Draw such a graph.
(b) What is the least number of edges we can add to K_4 to obtain a simple graph with an Euler cycle? (It will be necessary to add vertices, as well.) Draw such a graph.
(c) What is the least number of edges we can remove from K_4 to obtain a bipartite graph? Draw such a graph.
(d) Either draw a planar graph with 8 edges, 9 vertices, and 2 faces, or prove that there is no such graph.

4. Let G be the graph with vertex set V = {a, b, c, d, e} and with adjacency matrix

relative to alphabetical order on V.
(a) Is G planar? Be convincing.
(b) Does G have a Hamiltonian cycle? Be convincing.
(c) What is the least number of edges we can add to G, so that it will have an Euler cycle? Be convincing.
(d) What is the chromatic number of G? That is, what is the least number of colors needed to color the vertices so that adjacent vertices always have different colors? Be convincing.
(e) Give a function f : V --> V that is an isomorphism from G to itself, and is not exactly the same as the identity function on V.

5. Assume that G is a graph with two and only two vertices of odd degree, a and b (and an unspecified number of vertices of even degree). Show that there must be a path in G from a to b.

6. Assume that G is a connected graph that is isomorphic to the graph H. Prove that H is also connected. (That is, prove that connectivity is invariant under isomorphism.)

Click here for answers, after you have done the problems.