# Having trouble in understanding the definition of a clique

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.

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

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 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.

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