0

大学数学基礎解説

52

0

$$$$

Show that if $G$ is a connected planar graph with $n$ vertices, $m$ edges and $f$ faces, then

$$
n-m+f=2
$$

If $G$ is a connected planar graph with $n \geq 3$ vertices and $m$ edges, then $m \leq$ $3 n-6 .$ If additionally $G$ has no triangles, then $m \leq 2 n-4 .$

Show that $K_{5}$ is not planar

Show that For any vertex a of a graph $G$, the equality

$$
M(G)=M(G-a)+\sum_{b \in N(a)}\left(M\left(G_{a, b}+1\right)\right)
$$

holds.

Show that arbitrary graph $G$,

$$
T(G) \leq M(G)+1.
$$

Show that the Petersen graph is non-planar.

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
$$

投稿日：2021年5月1日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

コメント

コメントはありません。

読み込み中...

読み込み中