Find upper and lower bound for the size of a maximum (largest) independent set of vertices in an n-vertex connected graph, then draw three 8-vertex graphs, one that achieves the lower bound, one that achieves the upper bound, and one that achieves neither.
I have no idea about that, could anyone explain how to find and draw the upper and lower bound for me.
On
Here's a nudge in the right direction:
$K_8$ is the graph that needs to be considered for the lower bound. It has independent sets of size $0$ or $1$, and so a maximum independent set will have size $1$.
Obviously, an independent set of size $8$ is not possible (as for it to be independent, there would be have to be no edges in the graph, but then it would not be connected). But what about size $7$?
For the upper bound, note that deleting edges from cycles (a) does not disconnect the graph and (b) does not reduce the size of the maximum independent set. So we should consider trees. Is there an $8$-vertex tree with a maximum independent set of size $7$?
Finding an "in-between" graph: I suggest picking a connected graph with a non-edge and a triangle (a $K_3$ subgraph), and showing that these properties imply a maximum independent set size between the bounds.
HINT:
You have to find the connected graphs which have the extreme independent numbers. For the lower bound consider a graph where every vertex is adjacent to the rest of vertices. This leads to the complete graph $K_n$, with independence no. 1.
For the upper bound just think the opposite of the above scenario. No vertex is adjacent to any other vertex. This leads to $\overline{K_n}$, with ind. no. $n$. But this is disconnected.
So now look if $\alpha(G) = n-1$ is possible or not. For this you need $n-1$ vertices not adjacent to each other. To make it connected, join the last vertex to each of them.