Nonseparable Graphs

Cut Vertex:

ここで，c(G)はGの連結成分の個数

定理
頂点数が３以上の連結グラフがcut vertexを持たない⇔任意の二頂点がinternaly disjoint pathで連結
ここで，internaly disjoint pathとは，端点以外で共通の頂点を持たないpath

Separation:
ただ一つの頂点を共有して持つ非空で連結の二つの部分グラフへの分解のこと

定理
cut vertex⇒separating vertex
cut vertex⇔separating vertex (looplessの場合)

Nonseparable Graph:
連結かつseparating vertexが存在しないグラフのこと

定理
連結グラフがnonseparable⇔任意の二つの辺がある一つの共通のcycleに存在する

Blocks:
A subgraph which is nonseparable and is maximal with respect to the this property.

命題
a) Gの任意のブロックはたかだか一つの共有点を持つ
b) GのブロックはGの分解を成す
c) Gの各々のcycleは，Gのブロックに含まれる