Number of edges for a graph with $|V|=10$ and $c(G)=2$ $G$ is a graph with $|V|=10$ and $c(G)=2$. I am suppose to show that $8 \leq |E| \leq 36$, but I am not sure why a cycle would impose such restrictions on the number of edges.
So far the exercises have been assuming $G$ is simple, but since we have a cycle graph then I suppose not. Maybe the cycle graph is disconnected from the rest of $G$? Then the rest of the $10-2=8$ vertices have degree at most $8-1=7$. But then there would be at most $7\cdot 8 + 2 = 56+2 = 58$ total edges which breaks the upperbound given in the problem.
Can anyone offer advice?
--
SOLVED I don't know how to close this post, but apparently $c(G)$ means connected components. Hence if $c(G)=2$ then |E| would range from C(5,2)+C(5,2) = 20 to C(1,2) + C(9,2) = 36.
 A: For $G$ having 10 vertices and 2 components, $|E|=8$ is achieved by $Q=P_5+P_5$, the disjoint union of two 5-vertex path graphs. $|E|=36$ is achieved by $R=K_9+K_1$, the disjoint union of the 9-vertex complete graph and a single vertex. All numbers of edges between these two bounds can be achieved by deleting edges from $R$ or adding edges to $Q$.
To show that $|E|<8$ is not possible, note that adding an edge decreases the number of connected components by at most one. Starting from a graph $\overline{K_{10}}$ with ten vertices but no edges (and hence ten components), the least number of components we can get after adding seven edges is $10-7=3>2$, so no $G$ can have seven or fewer edges.
$|E|>36$ is also not possible because disconnecting the complete graph $K_{10}$ of 45 edges requires the removal of at least a complete bipartite graph $S=K_{p,10-p}$. The least number of edges $S$ can have is nine, corresponding to $p=1,9$, but it implies that $e(G)\le36$.
We have thus shown rigorously that $8\le|E|\le36$ for a $G$ with the given properties.
