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

• Are you sure $|Edges|\ge|Vertices|-|components|$ is the definition of a graph? What textbook are you using?
– bof
Jan 12 '18 at 11:36
• Have you tried to draw a graph with $6$ vertices, $11$ edges, and only one component? It shouldn't be that hard, why don't you just do it? I'm sure if you hand in a drawing of such a graph, you will get full marks.
– bof
Jan 12 '18 at 11:37

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.
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.
• That has a minimum for $n=3$. The maximum number of edges is when $n=1$ or $5$. Jan 12 '18 at 11:40