東京大学新領域創成科学研究科メディカル情報生命専攻 2018年8月実施問題10

Author

Description

Answer the following questions regarding undirected graphs. A simple graph is a graph that does not contain any multi-edges or self-loops. A walk is defined as a connected sequence of edges.

(1) Prove that, for any graph \(\mathbf{G}\), the number of nodes whose degree is odd is always even.

(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\).

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

(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\).

(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.

回答以下关于无向图的问题。简单图是指不包含任何多重边或自环的图。行走被定义为边的连接序列。

(1) 证明对于任何图 \(\mathbf{G}\)，度数为奇数的节点数总是偶数。

(2) 写出以下图的邻接矩阵 \(\mathbf{A}\)，并证明节点 1 和 4 之间长度为 2 的路径数等于 \(\mathbf{A}^2\) 的 \((1,4)\) 元素。

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

(3) 证明对于任何具有某个邻接矩阵 \(\mathbf{A}\) 的简单图 \(\mathbf{G}\)，节点 \(i, j\) 之间长度为 \(k\) 的路径数等于 \(\mathbf{A}^k\) 的 \((i,j)\) 元素。

(4) 假设一个简单连通图 \(\mathbf{G}\) 有两个或更多节点。证明 \(\mathbf{G}\) 至少有两个度数相同的节点。

Kai

(1)

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, \ldots, v_n\}\) and edges \(\{e_1, e_2, \ldots, e_m\}\), we have:

\[ \sum_{i=1}^n \deg(v_i) = 2m \]

where \(\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.

(2)

The given graph is:

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

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

\[ \mathbf{A} = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} \]

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} = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 3 & 1 & 1 & 2 \\ 1 & 2 & 2 & 1 \\ 1 & 2 & 2 & 1 \\ 2 & 1 & 1 & 3 \end{pmatrix} \]

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 \rightarrow 2 \rightarrow 4\)
\(1 \rightarrow 3 \rightarrow 4\)

(3)

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 \geq 1\).

(4)

This proof uses the Pigeonhole Principle.

Let \(\mathbf{G}\) be a simple connected graph with \(n\) nodes where \(n \geq 2\). The degree of a node (vertex) in a simple graph can range from \(0\) to \(n-1\). In a connected graph with \(n \geq 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.

Knowledge

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

重点词汇

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

参考资料

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

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2018年8月実施 問題10