10.5 #28

Note that $K_{m,n}$ has $m$ vertices of degree $n$ and $n$ vertices of degree $m$. We assume $m,n\ge 1$.

a) $K_{m,n}$ has an Euler circuit if and only if all vertices have even degree. This is true when $m$ and $n$ are even.

b) $K_{m,n}$ has an Euler path if and only if at most 2 vertices have odd degree. This is true when $m$ and $n$ are even, or when one of $m,n$ is 2, or when $m=n=1$.

10.5 #34

The graph does not have a Hamilton circuit.

Suppose that it did. Then $a$ must appear in the circuit, and the vertices immediately before and after $a$ must be $d$ and $b$ (in either order). Similarly, the vertices immediately before and after $c$ must be $b$ and $h$; the vertices immediately before and after $g$ must be $h$ and $f$; and the vertices immediately before and after $e$ must be $f$ and $d$. Thus all eight edges around the outer perimeter of the graph must be used in the Hamilton circuit. Moreover, since each vertex can only be visited once during the circuit, those eight edges must occur consecutively. But then no vertex in the interior of the graph can be visited.

10.7 #6

The graph is planar. There is no need to move any of the vertices; the edges $a—f$ and $c—d$ can be redrawn as curved arcs so that they do not intersect each other or the other edges.

10.7 #8

The graph is not planar, since the subgraph obtained by deleting vertices $g$ and $h$ is isomorphic to $K_{3,3}$. (Each of $a,c,e$ is adjacent to each of $b,d,f$.)

10.7 #16

A bipartite graph has no triangles, so Corollary 3 on page 723 gives the desired result.

10.7 #18

The formula is $r=e-v+k+1$.

To see why, let planar graph $G$ have $k$ connected components, $e$ edges, and $v$ vertices. Let the connected components be $G_1,G_2,\ldots,G_k$; let $v_i$ be the number of vertices of $G_i$, let $e_i$ be the number of edges of $E_i$, and let $r_i$ be the number of regions in a planar representation of $G_i$. Note that $e=e_1+e_2+\cdots+e_n$ and $v=v_1+v_2+\cdots+v_n$, because each edge or vertex of $G$ belongs to exactly one connected component. However, $r=(r_1-1)+(r_2-1)+\cdots+(r_k-1)+1$, because each interior (i.e. bounded) region of $G$ belongs to exactly one connected component, but the exterior (i.e. unbounded) region is common to all the connected components. Therefore, $r_1+r_2+\cdots+r_k=r+k-1$.

By Euler’s formula, we have $$r_1 = e_1-v_1+2$$ $$r_2 = e_2-v_2+2$$ $$\vdots$$ $$r_k = e_k-v_k+2$$ Adding up these equations gives $r+k-1=e-v+2k$. Subtracting $k-1$ from both sides gives $r=e-v+k+1$.