7
$\begingroup$

My definition says

A clique is a graph that has an edge connecting every pair of vertices

but as I understand, an edge connects only two vertices. Like $A-B$.

If we want to connect three vertices, we need at least two edges. For example, $A-B-C$.

I don't understand how an edge can connect every pair of vertices.

$\endgroup$
  • 2
    $\begingroup$ It's not one edge $e$ that connects all the pairs. For each pair $u,v\in V$ there is an edge $e_{uv}$ that connects the two nodes. That is, a clique is a (sub-)graph that contains all possible edges. $\endgroup$ – adrianN Dec 15 '16 at 14:55
12
$\begingroup$

Recalling that a clique is a subset $C$ of vertices of an undirected graph such that the subgraph induced by $C$ is fully connected. That is, every two distinct vertices in $C$ are connected by a distinct edge of the graph. This means different edges, not the same.

So, on a clique $C$ containing $k$ vertices $v_1, v_2,..,v_k$, there are $\frac{k(k-1)}2$ edges connecting them, that is the number of possible unordered pairs on $k$ elements.

Example

enter image description here

As you can see in the previous picture, this is a clique on four vertices $\{{1,2,3,4}\}$, so there is a different edge connecting every edge (i.e. $(1,2)$,$(1,3)$,$(1,4)$,$(2,3)$,$(2,4)$,$(3,4)$).

You can count them and see that there are exactly $6 = \frac{4\times 3}{2}$ edges.

$\endgroup$
  • 1
    $\begingroup$ How do you know there are k(k-1)/2 edges? $\endgroup$ – yashirq Dec 15 '16 at 15:03
  • 3
    $\begingroup$ For every 2 vertices there is an edge. How many pairs of vertices do you have from $n$? $\binom{n}{2}$ $\endgroup$ – Eugene Dec 16 '16 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.