Chapter 4 Graph Theory

Solution of 1:

We prove by induction on $m$. If $m=0$, then $G=K_1$, a graph with 1 vertex and 1 face. The formula is true in this case. Assume it is true for all planar graphs with fewer than $m$ edges and suppose $G$ has $m$ edges.

Case $1:G$ is a tree. Then $m=n-1$ and obviously $f=1$. Thus $n-m+f=2$, and the result holds.

Case $2:G$ is not a tree. Let $C$ be a cycle in $G$, and $e$ an edge in $C$. Consider the graph $G-e$. Compared to $G$ this graph has the same number of vertices, one edge fewer, and one face fewer (since removing $e$ coalesces two faces in $G$ into one in $G-e$ ). By the induction hypothesis, in $G-e$ we have $n-(m-1)+(f-1)=2$. Therefore, in $G$ we have $n-m+f=2$. Then completed the proof.

Solution of 2:

If we trace around all faces, we encounter each edge exactly twice. Denoting the number of faces of degree $k$ by $f_k$, we conclude that $\sum _{k}k{f}_k=2m.$ Since the degree of any face in a (simple) planar graph is at least 3 , we have
$$3f=3\sum _{k\ge 3}{f}_k\le \sum _{k\ge 3}k{f}_k=2m$$

With the Euler's formula, this proves that $m\le 3n-6$. If additionally, $G$ has no triangles, then
$$4f=4\sum _{k\ge 4}{f}_k\le \sum _{k\ge 4}k{f}_k=2m$$
and then we have $m\le 2n-4$.

Solution of 4:

The proposition is a consequence of the fact that each induced matching either is included in $G-a$ or contains an edge incident with the vertex $a$.

Solution of 5:

For the complete graph with $n$ vertices, we have $T\left(K_n\right)=n,M\left(K_n\right)=n(n-1)/2$ and the inequality is true for all $n$. If $G$ is not a complete graph, then it has a nondominating vertex $a$. The statement of the theorem is proved by induction on the number of vertices with the help of the lemma.
$$T(G)\le T(G-a)+\sum _{b\in N(a)}T\left(G_{a,b}\right)\le M(G-a)+1+\sum _{b\in N(a)}(M\left(G_{a,b}\right)+1)=M(G)+1$$