If an undirected graph $G = (V, E)$ has bounded degree $\deg(v) \leq d$ for each $v \in V$, how can we bound from above the number of connected components $C(G)$ of $G$?
The following very rough proof sketch argues that $$C(G) \leq |V| - \frac{|E|}{2\cdot d}.$$ Indeed, write $V^* \subset V$ for the number of vertices of positive degree; i.e., $V^* = \{ v \in V | \deg (v) > 0 \}$. We first argue that $C(G) \leq |V| - \frac{|V^*|}{2}$. Indeed, $|V^*|$ is identified under the reachability relation in at least a 2-1 manner (and more in general), and will decrease the number of connected components by $\frac{|V|}{2}$. Finally, $|V^*| \geq \frac{|E|}{d}$. The idea is that the $|E|$ total edges must be "distributed" among the elements of $V^*$; in the "worst" case, each vertex alone uses $d$ among those edges. (This doesn't really make sense because each edge belongs to two vertices, not one.)
Can we get a tighter bound? Can we get a more rigorous / elegant proof? Thanks.
Claim. In every simple graph with at least one vertex and degree bounded by $d$, we have $$ |V|-\frac{|E|}d\ge 1.$$
Proof. It is enough to prove the claim when $$d=\max\{\,\deg(v)\mid v\in V\,\}$$ as making $d$ larger makes the claim only weaker. Under this assumption, we have $$|E|\ge d$$ already from the edges incident with one vertex of maximal degree.
By the handshaking lemma (i.e., by counting the edge-vertex incidences in two ways), we have $$ d|V|\ge 2|E|$$ and so $$ |V|\ge\frac{2|E|}{d}.$$ This makes $$ |V|-\frac{|E|}{d}\ge \frac{2|E|}{d}-\frac{|E|}d=\frac{|E|}d\ge1$$ as was to be shown. $\square$
The claim holds per connected component so that we immediatyly improve it to $$ C(G)\le |V|-\frac{|E|}d.$$ Note that this inequality is sharp as witnessed by graphs where each component is $d$-regular (e.g., when $G$ consists of several disjoint copies of $K_{d+1}$).