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}=2 m .$ Since the degree of any face in a (simple) planar graph is at least 3 , we have
$$ 3 f=3 \sum_{k \geq 3} f_{k} \leq \sum_{k \geq 3} k f_{k}=2 m $$

With the Euler's formula, this proves that $m \leq 3 n-6$. If additionally, $G$ has no triangles, then
$$ 4 f=4 \sum_{k \geq 4} f_{k} \leq \sum_{k \geq 4} k f_{k}=2 m $$
and then we have $m \leq 2 n-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) \leq T(G-a)+\sum_{b \in N(a)} T\left(G_{a, b}\right) \leq M(G-a)+1+\sum_{b \in N(a)}\left(M\left(G_{a, b}\right)+1\right)=M(G)+1 $$