9
$\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.

Improve this question
$\endgroup$
1
  • 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
    Commented Dec 15, 2016 at 14:55

1 Answer 1

Reset to default
13
$\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.

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

Your Answer

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

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