私の定義によると
Aクリークは、頂点のすべてのペアを接続するエッジを持つグラフです
しかし、私が理解しているように、エッジは2つの頂点のみを接続します。 $ A-B $ のように。
3つの頂点を接続する場合は、少なくとも2つのエッジが必要です。たとえば、 $ ABC $ 。
エッジが頂点のすべてのペアを接続する方法がわかりません。
コメント
- 'すべてのペアを接続する1つのエッジ$ e $ではありません。ペアごとに$ u、v \ V $には、2つのノードを接続するエッジ$ e_ {uv} $があります。つまり、クリークは、考えられるすべてのエッジを含む（サブ）グラフです。
回答
クリークは、無向グラフの頂点のサブセット $ C $ であることを思い出してください。 $ C $ によって誘導されたサブグラフは完全に接続されています。つまり、 $ C $ の2つの異なる頂点ごとに接続されています。グラフの個別のエッジで接続されています。これは、同じではなく、異なるエッジを意味します。
したがって、 $ k $ を含むクリーク
例
前に示したように写真、これは4つの頂点 $ \ {{1,2,3,4} \} $ のクリークであるため、すべてのエッジを接続する異なるエッジがあります（つまり、 $（1,2）$ 、 $（1,3）$ 、 $（1,4）$ 、 $（2,3）$ 、 $（ 2,4）$ 、 $（3,4）$ ）。
それらを数えて、正確に存在することを確認できます $ 6 = \ frac {4 \ times 3} {2} $ エッジ。
コメント
- k（k-1）/ 2のエッジがあることをどのように知っていますか？
- 2つの頂点ごとにエッジがあります。 $ n $から頂点のペアはいくつありますか？ $ \ binom {n} {2} $