What is a Clique in Graph Theory?

[Tenshou]

Okay, so I just started reading a few books on Graph Theory and Topology (I wasn't sure if I should put this in Topology or here.), and I am just here to clear up some concepts, mainly about Cliques, to be precise what is a Clique? I have read Wikipedia articles and the books, and still No clear conceptual answer I am able to form. So is a Clique, like a sub graph with at least 2 vertices, or is it a sub graph that has a minimum number of vertices that are connected via an edge are at least 2?

I am not sure If I just said the same thing twice or what D: see I am a little confused on this topic. The books I am reading are Graph Theory by Bondy and Murty, Modern Graph Theory Bollobas (his Erdos number is 2 >:3), Topology by Basener, and finally Discrete Mathematics and its Applications by Rosen. These books help with understanding some of the other technical stuff but this is Clique concept is kinda... kinda dry? you know what I mean? And since I am reading this, you better believe I am serious about this Graph Theory stuff :3

 

[lurflurf]

A clique is a subset of vertices of a graph such that any to elements share an edge. If we use write ab when a and b share an edge. Suppose we have a set of vertices V then a graph G which is a subset of VxV. If U is a subset of V it is a clique if UxU is a subset of G. I know of no size restriction. The empty set and any set of one element are cliques, though uninteresting ones. In short if for all x and y in U xy is in G, U is a clique.

 

[Tenshou]

So, like a maximally complete sub graph or something?

 

[lurflurf]

I guess you could say that. Any complete subgraph is a clique so maximally complete sub graph and maximal clique are equivalent.

 

[Tenshou]

oh okay thank you so much, also one more thing say there is a graph with 5 edges does that mean it has 5 1-vertex Cliques and 1 5-vertex Clique?

 

[lurflurf]

How many vertices? Remember since a clique is a complete subgraph if it has n vertices it must have n(n-1)/2 edges. No clique can have 5 edges as a clique has a triangle number of edges
0,1,3,6,10,15,...

 

[Tenshou]

so if we were to work with $K_{5}$ where it has a vertex sex of 5 elements $\left(v_{1}, v_{2}, v_{3}, v_{4}, v_{5} \right)$ then a clique is a sub vertex set such that it contains $\left( ^{6} _{2}\right)$ vertices? n is that what you are getting at?

 

[lurflurf]

Are you mixing up vertices and edges?

A clique with n vertices has edges=n(n-1)/2=n choose 2=n \choose 2

Supposing your K5 is complete we have the following cliques
1 5-vertices cliques (10 edges)
5 4-vertices cliques ( 6 edges)
10 3-vertices cliques ( 3 edges)
10 2-vertices cliques ( 1 edges)
5 1-vertices cliques ( 1 edges)
1 0-vertices cliques ( 0 edges)

Kn if complete has cliques
n \choose k k-vertices cliques (k \choose 2 edges)

if we were to work with $K_{n}$ where it has a vertex sex of n elements $\left(v_{1}, v_{2}, v_{3}, v_{4}, v_{5},... \right)$ then a clique is a sub vertex set such that it contains k vertices and $\left( ^{k} _{2}\right)$ eges

 

[Tenshou]

But $\left( ^{n} _ {2}\right) = n^{2}-n$ and triangle numbers are $\left(^{n+1} _{2}\right)$ but all of the rest of the stuff I seem to understand, so you are saying that the number of k-vertices are just the binomial formula, gotcha!

 

[lurflurf]

{n \choose 2} =\frac{n!}{2!(n-2)!)}=n(n-1)/2

 

[Tenshou]

What do you mean? they don't really seem like they are the same.

 

[lurflurf]

They are {n \choose 2} \, \mathop{and} \, {{n+1} \choose 2} they are the same numbers shifted by one.0,1,3,6,10,15,...
1,3,6,10,15,21,...

 

[Tenshou]

But $n^2-n \neq (n^2-n)/2$ I still don't understand how they come from that.

 

[lurflurf]

{n \choose 2} =\frac{n!}{2!(n-2)!)}=n(n-1)/2
you have lost a 2

Just draw out a few small graphs it will become clear.

 

[Tenshou]

I see never mind, I was thinking of permutations, and not combinations D: thank you for you help!