K-頂点連結グラフ
1 2 Schrijver, Combinatorial Optimization, Springer
しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: n-頂点の完全グラフは、 頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、 独立な道に基づいた定義に従うと、その連結度は n − 1 になる。 そして、何人かの研究者は、連結度が n となるような代替的な定義を用いている。
1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。
グラフの頂点連結度あるいは単純に連結度とは、 そのグラフ k-頂点連結であるような k の最大数のことを言う。
任意のk-次元凸ポリトープのスケルトン(英語版)は、 k-頂点連結グラフを形成する(バリンスキーの定理、Balinski 1961)。 その部分的な逆として、シュタイニッツの定理(英語版)では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。