0
$\begingroup$

My question is about graph theory. Prove that a graph on $n$ vertices with $c$ components has at least $n-c$ edges.

$\endgroup$
1
$\begingroup$

Supose your graph has $c$ conected componentes, each with $n_1$, $n_2$, $\ldots$, $n_c$ vertices. Your graph as a whole has $n=n_1+n_2+\ldots+n_c$ vertices. Supose the components are conected by the fewest edges posibles. Any set of $k$ vertices can be conected by just $k-1$ vertices, as in path graphs, $K_{1,k-1}$ bipartite graphs, and so on; so the $i$-th component of your graph can be conected with at least $n_i-1$ edges. The sum of these numbers gives you a lower bound for the number of edges in the whole graph: $$\sum^{c}_{i=1}(n_i-1) =n_1+n_2+\ldots+n_c-c=n-c.$$

$\endgroup$
0
$\begingroup$

First we prove that if $c = 1$ (if the graph is connected) we have at least $n - 1$ edges. A simple path with $n$ vertices has $n - 1$ edges, thus it's possible. If $\delta \geq 2$, then we have at least $n$ edges, thus there is a node with $\delta = 1$. use induction on other vertices, so you have at least $n-2$ edges on other vertices of the graph and $n - 1$ edges on all vertices of the graph. Now, we have $c$ connected components with $a_i$ vertices on $i^{th}$ component. thus we have at least $\Sigma_{i = 1}^c (a_i - 1) = n - c$

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