隣接と接続

数学的な扱いを行う場合, それは集合の対であり, 図としての表現は意味をなさない.

そのため, 図として見れば自明な性質や状態に対しても, 厳密な定義を与える必要がある.

以下に示すのは, グラフの辺や頂点における最も基本的な性質, 頂点同士が辺で結ばれているか? と, 辺と頂点はつながっているか? を定義したものである.

\( G =(V, E) \) をグラフとする.

定義：隣接

\( G\) の２頂点 \(a\), \(b\) が \( G \) 上で隣接している, とは \( G \) に辺 \(\{a, b\}\) が存在することである

定義：接続

\( G \) の頂点 \( v \) と辺 \( e \) において, \( v \in e\) が成り立っているとき, \( G \) 上で \( v \) と \( e \) は接続していると言う.

\( 2 \) つの頂点が同じ辺に接続していれば, それらは隣接している.

これを上記の定義を用いて証明すると, 以下のようになる.

定理

頂点 \(a\) と \(b\) がともに同じ辺に接続しているならば, 

\(a\) と \(b\) は隣接している.

証明

\(a\) と \(b\) がともに接続している辺を \( e\) と置く.

\(a\) と \(e\) が接続しているので, 接続の定義から \( a \in e \) であり, 同様に \( b \in e \) でもある.

\( a \in e \) かつ \( b \in e \) なので \( \{ a,b \} \subseteq e\) である

もし \( \{ a,b \} \subsetneq e\) ならば \( e \) の要素数が \(2\) を超えてしまうので, \( \{ a,b \} \subsetneq e\) ではない.(\( e \) は辺なので, 丁度 \( 2 \) 個の頂点しか要素として持たない.)

\( \{ a,b \} \subseteq e\) であり, \( \{ a,b \} \subsetneq e\) ではないので \( \{ a,b \} = e\) である.

\( e \) は \( G \) の辺であり, \( \{ a,b \} = e\) なので, \( \{ a,b \}\) は \( G \) の辺である.

定義より, 頂点 \( a \) と \( b \) は接続している

証明終