1
$\begingroup$

Suppose $G$ and $G'$ are two graphs having $n$ vertices.For what values of $n$ is it possible for $G$ to have more components and edges than $G'$?

What could be the possible values of $n$?

$\endgroup$
1
$\begingroup$

If $n=1,2,3,4$ it's not possible.

If $n$ is $5$ consider $K_4$ with an isolated vertex and $P_5$, one has $6$ edges and $2$ components, the other $4$ edges and $1$ component.

If $n$ is greater than $5$ consider $K_4$ and $n-4$ vertices and $P_5$ with $n-5$ isolated vertices.

$\endgroup$
  • $\begingroup$ K4 will have 6 edges and P5 will have 4 edges according to above explanation $\endgroup$ – Priyaranjan Dec 23 '14 at 21:49
  • $\begingroup$ Oh yeah, right. $\endgroup$ – Jorge Fernández Hidalgo Dec 23 '14 at 21:57
  • $\begingroup$ Still p5 show 5 edges..it should be 4,i think you forgot to edit $\endgroup$ – Priyaranjan Dec 23 '14 at 22:05
  • $\begingroup$ Oh oops, the example still works though :) $\endgroup$ – Jorge Fernández Hidalgo Dec 23 '14 at 22:23
1
$\begingroup$

It is possible for $n\ge 5$.

We might have $G'$ connected (so a single component) with as few as $n-1$ edges (tree).

Then $G$ could have an isolated vertex and a clique (complete subgraph) on the remaining $n-1$ vertices. Now $(n-2)(n-1)/2 \gt n-1$ for $n-2 \gt 2$, i.e. $n \gt 4$.

$\endgroup$
  • $\begingroup$ We posted almost at the same time :) (you won by a couple secs) $\endgroup$ – Jorge Fernández Hidalgo Dec 23 '14 at 6:06

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.