1.
(a) The average degree must be 1.8.
The number of edges is 9, and the sum of the degrees
is twice that. So the average is 18/10.
(b) The average degree must be 3.2.
By Euler's formula for planar graphs, the number of
edges is 16. Proceed as before.
2. G is the weighted graph in
Exercise 4 of the section Minimal Spanning Trees.
Applying Dijkstra's algorithm to find a
shortest path from 1 to 12
explores the vertices in the following order:
1, 5, 2, 8, 6, 4, {3, 10}, {7, 9}, 11, 12.
Braces indicate ties.
3. (a) Two. There are four vertices of odd degree in K_4. Each added edge can take care of only two of them.
(b) Four. Those four vertices of odd degree are all adjacent in K_4. Each added edge can now take care of only one of them. K_5 is such a graph.
(c) Two. K_2,2 is such a graph. If we remove only one edge (it doesn't matter which one; we get isomorphic graphs no matter which we remove), there is still a triangle.
(d) Yes, there are planar graphs with e = 8, v = 9, and f = 2.
By Euler's formula, the graph must have two components.
One such graph has one component that is K_3 and another
that looks like this:
o -- o -- o -- o -- o -- o
4.
(a) Yes, G is planar. One way to show this is simply
to draw it without crossing edges. Besides, every seven-edge
graph is planar.
(b) Yes, H has Hamiltonian cycles. Here is one:
a -- b -- c -- e -- d -- a
(c) Two edges. (But if you want a simple graph,
then three edges must be added.) G has four vertices of odd degree.
(d) Three colors. G has a K_3 subgraph, so it is not
2-colorable. Color a and e red; color b and d blue;
color c green.
(e) There are three such functions. Here is one:
f(a) = a, f(b) = d, f(d) = b, f(c) = c, f(e) = e
5. Assume that G is a graph with two and only two vertices of odd degree, a and b. We want to show that there is a path in G from a to b.
First proof. Suppose to the contrary there is no such path.
Then a's component is a subgraph with only one vertex
of odd degree. Hence the sum of the degrees in this component
is odd, contradicting the fact that the sum equals twice the
number of edges.
So there must have been a path from a to b after all.
Second proof. Start at a, and follow any path without repeated edges, until you get stuck. As in our proof of Euler's theorem, you cannot get stuck at a vertex of even degree. (You come in to the vertex on an edge; now there are an odd number of edges left; zero is not odd.) And similarly you cannot get stuck at a (which has even degree after you erase the starting edge). Conclusion: You get stuck at b. And now you have made a path from a to b.
6. G is a connected graph. H is an isomorphic graph; say f is an isomorphism from G to H. We want to prove that H is also connected.
Consider two arbitrary vertices u and w in H. We want to show there is a path from u to w in H. Because f is onto, we have f(x) = u and f(y) = w for some vertices x and y in G. We know there is a path (say of length n) from x to y in the connected graph G: