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

3 Answers 3

14
$\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$
1
  • $\begingroup$ nice answer.................. +1 $\endgroup$
    – TShiong
    Commented Jan 29, 2023 at 18:57
10
$\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$
0
6
$\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$
2
  • $\begingroup$ That has a minimum for $n=3$. The maximum number of edges is when $n=1$ or $5$. $\endgroup$ Commented Jan 12, 2018 at 11:40
  • $\begingroup$ You are right, my mistake, thank you for correction. $\endgroup$
    – ArsenBerk
    Commented Jan 12, 2018 at 11:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .