1
$\begingroup$

Minimum number of components in graph where we have 69 vertices and 43 edges. I think the best way is to create a path? One path and the rest would be isolated components. Since in path we use only one edge for 2 vertices. Correct?

$\endgroup$
1
$\begingroup$

Yes, this is correct.

The easiest way to get to the result is to look at a graph with $v$ vertices and $0$ edges. It obviously has $v$ components. Adding an edge between two vertices $a$ and $b$ reduces the number of components if $a$ was not reachable from $b$ before adding the new edge.

Concerning "best" solution: Your approach yields an optimal solution, though it is only one way to do it - there are other ways (e.g. 26 components with either 2 or 3 vertices) that work equally well.

$\endgroup$
1
$\begingroup$

It looks like you are on the right track.

Let us use a bit of arithmetic or counting to find the minimum number of components.

Suppose that graph has $k$ connected components that have $v_1, v_2, \cdots, v_k$ vertices and $e_1, e_2, \cdots, e_k$ edges, respectively. Then we know $v_1 + v_2 + \cdots + v_k = 69$ and $e_1+e_2+\cdots+e_k=43$.

What is the relation between the number of vertices and the number of edges in each connected component? I would assume you have learned the fact that the latter must be at least the former minus one. If you have not learned it, it can be proved easily by mathematical induction on the number of vertices.

  • The base case when there is only one vertex is clear.
  • For the induction step where you add a new vertex, at least one new edge is needed to connect the new vertex to the existing vertices.

So $e_i\ge v_i-1$ for all $i$. If you sum all such inequalities, you will get $43\ge 69-k$, which means $k\ge26$.

I will let you check when the equality $k=26$ holds. Hint, it holds if and only if all inequalities are equalities. What does an equality here mean?

$\endgroup$

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.