11
$\begingroup$

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$

$\endgroup$
  • 3
    $\begingroup$ Are you sure $|Edges|\ge|Vertices|-|components|$ is the definition of a graph? What textbook are you using? $\endgroup$ – bof Jan 12 '18 at 11:36
  • $\begingroup$ 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. $\endgroup$ – bof Jan 12 '18 at 11:37
11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That has a minimum for $n=3$. The maximum number of edges is when $n=1$ or $5$. $\endgroup$ – Especially Lime Jan 12 '18 at 11:40
  • $\begingroup$ You are right, my mistake, thank you for correction. $\endgroup$ – ArsenBerk Jan 12 '18 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.