Simple graph with 6 vertices and 11 edges 
Show that a simple graph with $6$ vertices, $11$ edges, and more than one component cannot exist.

I don't understand why can't there be a simple graph with those edges and vertices. By definition of graph we have $|\text{Edges}| \geq |\text{Vertices}|-|\text{components}|$
So from this definition it's correct: $11 \geq 6-w$
 A: Suppose for a contradiction, there exists a graph $G$ with $e$ edges satisfying given conditions and assume there are two disconnected components. Then by Handshaking Lemma, maximum number of edges that $G$ has is
$$e \le \binom{n}{2}+\binom{6-n}{2} = \frac{n(n-1)}{2}+\frac{(6-n)(5-n)}{2} = n^2-6n+15$$
which has maxima for $n = 1$ or $n = 5$ ($n=6$ is not possible since we assumed there are two components). And for both $n=1$ and $n = 5$, $e = 10$. So the maximum number of edges that $G$ can have is $10$, which is a contradiction a required.
A: If a component has only one vertex it has no edges, and the remaining five vertices can have at most 10 edges.
If a component has two vertices it gets worse since that component has only one edge, and the remaining 4 vertices have at most 6 edges. Other cases just as bad.
A: Hint: How many edges can there at most be in a simple graph component with $n$ vertices? Now apply this to a graph whose six vertices are partitioned into at least two components, and you should have your answer.
