Minimum & maximum options for simple graph connected component

Question

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!

Answer 1

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

• If $k=8$ then $n=16$ and all components must have 2 vertices, which is not true since some vertices have degree 2 or 3. So this is impossible.
• If $k=6$ and $n=14$ then this is possible by taking $G$ as union of five $K_2$ and one $K_4$
• A little bit of case work we see that $k=7$ is impossible.

So $k_{\max} =6$.

Answer 2

Quick heuristic, which I think (but don't have a formal proof) is valid. I also think the inequalities become equalities in many cases. $C$ is the set of components. $$\min{|C|} \geq \min{|V|} - \max{|E|} \\ \max{|C|} \leq \max{|V|} - \min{|E|}$$

For your problem, there are exactly 10 vertices of degree 1, the sum of degrees is $11\times2 =22$, and the remaining vertices can have degrees of only 2 or 3. So there must be 4 (all degree 3) to 6 (all degree 2) additional vertices. Hence, $|E|=11$ and $14 \leq |V| \leq 16$. Then we can get quick bounds on number of components by applying the above heuristic. $$3 \leq |C| \leq 5$$

Explanation

For minimum components, we want maximum edges and minimum vertices. So for a graph with $|E|=11$ and $|V|=14$, there can be no fewer than $|V|-|E|=3$ connected components. I don't know if there's a theorem for this, but one logic is to start with an empty graph containing just your vertices but no edges. Then the number of components is equal to number of vertices. Now add the edges one by one. Each edge will connect two vertices either in the same component (thereby maintaining the number of components) or in different components (joining them and decrementing the number). So for minimal components, we want each added edge to connect different components. Starting with 14 vertices and adding 11 edges, we can get down to atmost 3 components. This logic is how I learnt the proof for why a tree has $n-1$ edges.

Although, I don't know if the above logic is sufficient to guarantee the existence of a graph with 3 components, given the constraints on degrees. The way I created the example was to first start with a graph with only the 4 '$deg>1$' vertices out of the 14 minimal, then add a degree 1 vertex to satisfy the degrees, resulting in 4 components. But this graph has 12 degree-1 vertices, 2 more than allowed. So I eliminate 2 by merging 2 degree-1 vertices from different components, and their edges, to yield a valid graph with 3 components. This kind of thinking is inspired by organic chemistry: "Imagine you have 4 nitrogen atoms and 10 hydrogen atoms. Can you make 3 molecules?". My example is $NH_3, NH_3, H_2NNH_2$.

Continuing this organic chemistry train of thought, the analogous problem statement is

Using any number of O and N atoms, but using exactly 10 H atoms and 11 single bonds, what is the minimum and maximum number of acyclic molecules you can create?

For the maximum number of components, consider $|V|=16$: 10 degree-1 and 6 degree-2. Similar to the minimal components explanation, start with an empty graph containing just the 16 vertices but no edges; so 16 components. Now add the edges one by one. If the added edge connects two vertices in the same component, then it creates a cycle (since those two vertices were already connected in the component). Since our final graph is not allowed any cycles, each added edge must connect two vertices in different components. Therefore, the number of components must exactly reduce to $16-11=5$. The organic chemistry example is $4H_2O + HOOH$.

Therefore the number of components possible is 3 - 5.