CBMS-2019-10

题目来源：[[做题/文字版题库/CBMS/2019#Question 10|2019#Question 10]] 日期：2024-07-26 题目主题：CS-离散数学-图论

Solution

Question 1: Prove that, for any graph $\mathbf{G}$, the number of nodes whose degree is odd is always even

To prove this statement, we will use the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges. Mathematically, for a graph $\mathbf{G}$ with vertices $\{v_1,v_2,\dots ,v_n\}$ and edges $\{e_1,e_2,\dots ,e_m\}$, we have:

$$\sum _{i=1}^n\mathrm{deg}(v_i)=2m$$

where $\mathrm{deg}(v_i)$ is the degree of vertex $v_i$.

Now, consider the sum of the degrees of all vertices. Each degree is either even or odd. Let’s denote the number of vertices with odd degree as $n_{odd}$ and the number of vertices with even degree as $n_{even}$. Therefore, we have:

$$n_{odd}+n_{even}=n$$

Since the sum of the degrees is even (because it equals $2m$), and the sum of an even number of even numbers is even, the sum of an even number of odd numbers is also even. Therefore, the number of odd-degree vertices, $n_{odd}$, must be even.

Thus, the number of nodes whose degree is odd is always even.

Question 2: Write the adjacency matrix $\mathbf{A}$ of the following graph, and show that the number of walks of length 2 between nodes 1 and 4 is equal to the $(1,4)$-element of ${\mathbf{A}}^2$

The given graph is:

  1 -- 2
  | \  |
  |  \ |
  3 -- 4

The adjacency matrix $\mathbf{A}$ of this graph is:

$$\mathbf{A}=\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 1& 1& 1& 0\end{array}\right)$$

To find the number of walks of length 2 between nodes 1 and 4, we need to compute the matrix ${\mathbf{A}}^2$:

$${\mathbf{A}}^2=\mathbf{A}\cdot \mathbf{A}=\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 1& 1& 1& 0\end{array}\right)\cdot \left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 1& 1& 1& 0\end{array}\right)=\left(\begin{array}{cccc}3& 1& 1& 2\\ 1& 2& 2& 1\\ 1& 2& 2& 1\\ 2& 1& 1& 3\end{array}\right)$$

The $(1,4)$-element of ${\mathbf{A}}^2$ is 3, which means there are 3 walks of length 2 between nodes 1 and 4. The walks are:

1. $1\to 2\to 4$
2. $1\to 3\to 4$

Question 3: Prove that, for any simple graph $\mathbf{G}$ with some adjacency matrix $\mathbf{A}$, the number of walks of length $k$ between nodes $i,j$ is equal to the $(i,j)$ element of ${\mathbf{A}}^k$

We use induction on $k$ to prove this statement.

Base case: For $k=1$, the number of walks of length 1 between nodes $i$ and $j$ is given by the adjacency matrix $\mathbf{A}$. If there is an edge between $i$ and $j$, then ${\mathbf{A}}_{ij}=1$, otherwise ${\mathbf{A}}_{ij}=0$. Hence, the number of walks of length 1 between nodes $i$ and $j$ is ${\mathbf{A}}_{ij}$, which is the $(i,j)$ element of $\mathbf{A}$.

Inductive step: Assume the statement is true for $k=m$, i.e., the number of walks of length $m$ between nodes $i$ and $j$ is the $(i,j)$ element of ${\mathbf{A}}^m$. We need to show it is true for $k=m+1$.

The number of walks of length $m+1$ from node $i$ to node $j$ is the sum of the walks of length $m$ from $i$ to all intermediate nodes $k$ and then taking one step from $k$ to $j$. Mathematically, this is:

$$({\mathbf{A}}^{m+1}{)}_{ij}=\sum _{k=1}^n({\mathbf{A}}^m{)}_{ik}\cdot {\mathbf{A}}_{kj}$$

This is precisely the matrix multiplication of ${\mathbf{A}}^m$ and $\mathbf{A}$, and the result is the $(i,j)$ element of ${\mathbf{A}}^{m+1}$.

By induction, the number of walks of length $k$ between nodes $i$ and $j$ is equal to the $(i,j)$ element of ${\mathbf{A}}^k$ for all $k\ge 1$.

Question 4: Assume that a simple connected graph $\mathbf{G}$ has two or more nodes. Prove that $\mathbf{G}$ has at least two nodes with identical degree

This proof uses the Pigeonhole Principle.

Let $\mathbf{G}$ be a simple connected graph with $n$ nodes where $n\ge 2$. The degree of a node (vertex) in a simple graph can range from $0$ to $n-1$. In a connected graph with $n\ge 2$, no node can have degree 0, so the possible degrees range from $1$ to $n-1$.

However, we now have $n$ vertices but only $n-1$ different possible degrees. According to the Pigeonhole Principle, if we assign $n$ different items (in this case, vertices) into $n-1$ different categories (possible degrees), at least one category must contain more than one item.

Therefore, there must be at least two vertices in the graph that share the same degree.

知识点

图论邻接矩阵鸽巢原理抽屉原理数学归纳法

重点词汇

• degree 度
• adjacency matrix 邻接矩阵
• walk 步长
• connected 连通
• simple graph 简单图
• pigeonhole principle 鸽巢原理

参考资料

1. “Introduction to Graph Theory” by Douglas B. West, Chap. 1 and 2
2. “Discrete Mathematics and Its Applications” by Kenneth H. Rosen, Chap. 10