Let $G = \langle V, E \rangle$ be a simple graph with no simple circles.
Suppose that $|E| = 11$ s.t for each $u \in V : deg(u) \in$ {$1, 2, 3$}.
Moreover, there are exactly $10$ vertices with degree of 1 in the graph $G$.Find the minimal & maximal number of connected components in $G$.
I showed that $G$ is not connected itself (namely, it has at least two connected components) by bounding the sum of the degrees, which equals to $22$ (under these assumptions). Then, I argued there are at least three connected components by the way of contradiction & using the observation that although $G$ is not a tree itself, each component of it is a tree, and by denoting $x_1, y_1$ the number of vertices and edges respectively of the component $R_1$. Then it followed that $|V| = 13$ but this is impossible since $22 = 2|E| \leq 10 + (3 + 3 + 3) = 19$.
I found an example for 3 components and then found the maximum by using the same observation above, which implies there are at least 2 leafs at each component.
I feel like I couldve abstracted it more or found the lower bound at once instead of going one after one. I've already solved some questions of the same type and sometimes the lower bounds are higher which requires a lot more effort. I'll be glad if someone who is more experienced could've shed some light\point out some observations I can make at these problems which I haven't.
Thanks!
Best Answer
Let $d_i$ be a number of vertices of degree $i$. Then the number of vertices is $$n= 10+d_2+d_3$$ By handshake lemma we have $$2|E| = d_1 +2d_2+3d_3\implies 2d_2+3d_3 = 12 \implies d_2\in\{0,3,6\}\wedge d_3\in \{4,2,0\}$$ So $n\in \{14, 15, 16\}$.
Let $k$ be the number of connected components. Then we have $$|E_i|\geq n_i-1$$ ($n_i$ the number of vertices in $i$-th component), for each component. Thus $$11\geq n-k \implies k_{\min} \in\{3,4,5\}$$
Since there is no isolated points every component must have $n_i\geq 2$ and at so we have $$2k\leq n_1+n_2 +...+n_k = n\leq 16$$ so $k\leq 8$.
So $k_{\max} =6$.