# Two finite graphs with n vertices: Can one have both more components and more edges than the other?

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

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.

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

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

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