A graph $G=(V,E)$ is said to be critical if for every edge $e$ not in $E$, adding $e$ to $G$ creates a new copy of $K_{10}$.
Find a critical graph on $n$ vertices with ${n\choose 2}-{n-8\choose 2}$.
Show that if $G$ is a critical graph on $n$ vertices then $|E|\geq {n\choose 2}-{n-8\choose 2}.$ Hint: use Bollobas's theorem. The one mentioned here http://uniformlyatrandom.wordpress.com/2008/11/15/a-theorem-of-bollobas/
For the first question I have an idea, let's build n/10 connected components so they all are $K_{10}$ and remove one edge. this will give us $K_{9}$ in all of them - when we add back the edge we get $K_{10}$. Between every component - let's between component A and component B. For every vertex in A we'll add 8 edges to B (doesn't matter which as long as they go from A to B). If we add another edge to go from A to B we'll get an edge from A with the degree 9 (as needed). also we already know each vertex in B had the degree 8 at least. If the edge "hit" a vertex in B with the degree 8 - this new edge will be the 9 - so we got 10 vertices which all of them have the degree 9.
Can't really understand how to infer the amount ${n\choose 2}-{n-8\choose 2}.$ Also can't explain what happens if n modulo 10 isn't 0. Have no idea how to solve 2.
I think I have a solution. Take 8 vertices in random and connect them to every other vertex in G. So you have 8 vertices with the degree n-1. Every other vertex has the degree 8. Adding one edge will create 2 edges with a degree 9 + the 8 "original" vertices that are connected to them with degree of n-1. The number of edges in a complete n Graph MINUS the number of edges not in the graph is the answer.
If someone can help with question 2 or tell me why I couldn't add this to "answers" tab