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
👉 For more insights, check out this resource.
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?
👉 Discover more in this in-depth guide.
1 Answer
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.