# Graph Theoretic Stuff

1. Jun 21, 2013

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

2. Jun 21, 2013

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

3. Jun 21, 2013

### Tenshou

So, like a maximally complete sub graph or something?

4. Jun 21, 2013

### lurflurf

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

5. Jun 21, 2013

### 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?

6. Jun 22, 2013

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

7. Jun 22, 2013

### 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?

8. Jun 22, 2013

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

9. Jun 22, 2013

### 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!

10. Jun 22, 2013

### lurflurf

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

Last edited: Jun 22, 2013
11. Jun 22, 2013

### Tenshou

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

12. Jun 22, 2013

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

13. Jun 22, 2013

### Tenshou

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

14. Jun 22, 2013

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

15. Jun 22, 2013

### Tenshou

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