Notes

Does counting the number of edges in the graph already determine something about cliques?

If you have a graph of N nodes and want a clique of n, you need at least n(n-1)/2 edges. That's the minimum to connect n nodes: consider 4 nodes, 1st needs to connect to 3, 2nd needs to connect to 2 (already connected to first), 3rd needs to connect to 1, and 4th is already connected to the others. 3+2+1 = 4(3)/2, and n+(n-1)+(n-2)+...1=n(n-1)/2. But that many edges does not Guarantee a clique. What is the minimum number of edges that does?
- don't count redundant edges (connecting same two nodes) or else it could be infinite
- you'd have to have all nodes be part of a clique of size n-1
- but that's not sufficient. Ex: 10 nodes can have two 5-cliques; adding an edge doesn't make a 6-clique.
- at minimum that's (n-1)(n-2)/2 edges.
- there'd have to be one edge missing from a clique of size n
- at minimum that's (n)(n-1)/2 - 1 edges
- those minimums are less than our minimum needed to make an n-clique! But they're true for the n=N case.
- so the difference between N and n is relevant in the formula.

Perhaps "N choose n" is relevant: N!/(n!(N-n)!) is how many ways you can choose n nodes out of N nodes. I'll call it C.
C*n(n-1)/2 is how many edges could be drawn to make n cliques, but a lot of those are redundant.



The most number of edges we could have to not form a clique of n would involve all N nodes connected to all other nodes, except that the minimum amount of edges are missing, to disconnect any cliques of n. For N nodes and a clique of N, just one edge would have to be missing. For a clique of N-1, how many would we have to take out? Well, the lost edge in the N case makes it so two nodes are at a clique disadvantage; they still form a clique of N-1 though. All nodes would form an N-1 clique. Now symmetry is lost, and there are two ways I can remove an edge. Remove one from one of the diminished nodes, or remove one from a node that hasn't been touched. I'll need to visualize this.