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.

  • 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, 2016 at 14:55

1 Answer 1


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.


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.

  • 1
    $\begingroup$ How do you know there are k(k-1)/2 edges? $\endgroup$
    – yashirq
    Dec 15, 2016 at 15:03
  • 4
    $\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, 2016 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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