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

Author

水月, 祭音Myyura

Description

無向グラフに関する以下の問題に答えよ。

(1) 完全 \(3\) 部グラフ \(K_{r,s,t}\) とは、それぞれに属する点の個数が \(r, s, t\) である三つの点集合からなり、異なる集合に属する二点は全て辺で結ばれており、同じ集合に属する二点は辺で結ばれていないグラフである。 \(K_{2,2,2}\) を描け。

(2) \(K_{r,s,t}\) の辺の数を示せ。

(3) \(n\) をグラフの点数、\(m\) をグラフの辺数とする。単純グラフとは、ループと多重辺が存在しないグラフである。 また、\(\binom{a}{b}\) は、\(a\) 個の元から \(b\) 個選んで得られる組み合わせの数を表す。 以下の式を満たす単純グラフは、連結であることを示せ。

\[ m > \binom{n-1}{2} \]

(4) オイラーグラフとは、オイラー閉路を持つグラフを指す。オイラーグラフにおいては、全ての点の次数が偶数になることを示せ。

(5) 連結グラフにおいて、全ての点の次数が全て偶数であれば、オイラーグラフとなることを示せ。

Kai

(1)

(2)

\[ K_{r,s,t} = r(s + t) + st = rs + rt + st \]

(3)

Let \(G\) denote a simple undigraph of \(n\) vertices and \(m\) edges.

Assume that \(G\) is not connected, and hence there are at least two connected components in \(G\). It is trivial to see that the more number of connected components in \(G\), the less number of edges in \(G\). Hence w.l.o.g we assume that there are only two connected components (namely \(G_1\) and \(G_2\)), in \(G\).

Let \(n_1\) and \(n_2\) denote the number of vertices, \(m_1\) and \(m_2\) denote the number of edges of \(G_1\) and \(G_2\), respectively. Since a complete simple undigraph of \(n\) vertices has \(\binom{n}{2}\) edges, we have

\[ \begin{aligned} m_1 + m_2 &\leq \binom{n_1}{2} + \binom{n-n_1}{2} \\ &= \frac{n_1(n_1 - 1)}{2} + \frac{(n-n_1)(n-n_1-1)}{2} \\ &= \frac{1}{2} [(n_1^2 - n_1) + n(n-n_1-1) - n_1(n-n_1-1)] \\ &= \frac{1}{2} [n_1^2 - n_1 + n(n-1) - nn_1 - nn_1 + n_1^2 + n_1 + (2n-2) - (2n-2)] \\ &= \frac{1}{2} [n(n-1) + 2n_1^2 -2nn_1 + 2n-2 - 2(n-1)] \\ &= \frac{1}{2} [(n-1)(n-2) + 2(n_1^2 - 1) - 2n(n_1 - 1)] \\ &= \frac{1}{2}(n-1)(n-2) + (n_1-1)(n_1 - n + 1) \\ &\leq \frac{1}{2}(n-1)(n-2) \qquad (\because n_1 - n + 1 \leq 0) \\ &= \binom{n-1}{2} \end{aligned} \]

Hence a disconnected graph can have at most \(\binom{n-1}{2}\) edges. Therefore, if a simple undigraph of \(n\) vertices has more than \(\binom{n-1}{2}\) edges, then the graph is connected.

(4)

Since the number of incoming edges and the number of outgoing edges of a vertex in a cycle must be the same, a vertex appearing \(k\) times in an Euler cycle must have degree \(2k\).

(5)

We prove the claim by induction on the number of vertices \(n\).

For \(n = 2\), the graph must be two vertices connected by two edges. It has an Euler circuit.

For \(n > 2\), let \(G=(V,E)\) denote the graph. Let \(v \in V\) be an arbitrary vertex. Pick an arbitrary edge adjacent to \(v\). Continue to pick edges and walk around the graph until we return to \(v\) (we will never get stuck since every vertex has even degree, if there is an incoming edge, there is an outgoing edge). Let \(C_v\) be the circuit we found in above process.

Consider the graph \(G_v = G - C_v\). If \(G_v\) is empty, then \(C_v\) is an Euler circuit. Suppose that \(G_v\) is not empty. Obviously each vertex in \(G_v\) has even degree and the number of edges in \(G_v\) is less than \(G\). Hence by induction, we can find an Euler circuit for each connected component of \(G_v\).

Since \(G\) is connected, each of these sub-circuits shares a vertex with \(C_v\). We can join these circuits together at the shared vertex to form a circuit of all edges in \(G\), which is an Euler circuit.