I was asked to check if there are a graph with the following condition?

(a) It has $3$ components, $20$ vertices and $16$ edges

(b) It has $7$ vertices, $10$ edges, and more than two components.

However I am really confused with the definition of component, the definition I have checked is

a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths

And then when I am trying to find a graph in (a), its always easy to find more than $3$ subgraph in a big graph with $20$ vertices, so ill assume the answer is no. But how should I prove this or am I doing it completely wrong?

  • $\begingroup$ Connected graph edges are at least the number of vertices minus one. The minimum of edges is achieved for trees. $\endgroup$ – Somos Feb 25 at 5:20
  • 1
    $\begingroup$ Your definition of component is seriously wrong. What is your source for that definition? Did you quote it exactly word for word? $\endgroup$ – bof Feb 25 at 7:56

Answer for (a)

Say we have $a,b,c$ vertices in components, so $a+b+c+=20$. Then each component must have at least $a-1$, $b-1$ and $c-1$ edges, so we have at least $$a-1+b-1+c-1 = 17$$ edges. A contradiction.

Answer for (b)

It is possible, take $K_5$ and two isolated vertices.

  • $\begingroup$ Is this answer any help for you? $\endgroup$ – Aqua Feb 25 at 19:42
  • $\begingroup$ Yes this answer help a lot!! Thanks $\endgroup$ – Thomas Mar 2 at 16:50
  • $\begingroup$ Do you mind accepting the answer then? $\endgroup$ – Aqua Mar 2 at 16:51
  • $\begingroup$ Sorry im a new user, what does this mean? $\endgroup$ – Thomas Mar 2 at 17:03
  • 1
    $\begingroup$ Thomas, please do use upvote whenever you think the answer is usefull for you. Also at the most usefull answer mark the tick. This is the way to say thank you on this site and is somehow a pay for a poster who spend a time and effort to answer you. $\endgroup$ – Aqua Mar 3 at 0:12

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.