Let $G = (V, E)$ is a connected graph $\Rightarrow$ $\alpha(G) \le \frac{|E|}{\delta(G)}$, where $\alpha(G)$ is the vertex independence number of $G$ and $\delta(G)$ − minimum degree of all vertices.
Give some clue please!
Thanks anyway!
Let $G = (V, E)$ is a connected graph $\Rightarrow$ $\alpha(G) \le \frac{|E|}{\delta(G)}$, where $\alpha(G)$ is the vertex independence number of $G$ and $\delta(G)$ − minimum degree of all vertices.
Give some clue please!
Thanks anyway!
This is a rather easy application of the hand-shaking lemma.
Separate the graph $G$ into independent vertex sets. Suppose $S$ is the largest such set. Then since $G$ is connected, each vertex of $S$ must be connected to another, but no vertices of $S$ are adjacent to each other since the set is by assumption independent. Consider the set $T = S\cup N(S)$, the set of vertices of $S$ with all their connected neighbors $N(S)$. If we apply the handshaking lemma to $T$ $2|E(G)|\ge2|E(T)| = \sum_{v\in V(T)}\deg(v)=2\sum_{v\in V(S)}\deg(v) \ge 2\alpha\delta$ The second equality is given as follows. For each degree we introduce in the vertices of $S$, we necessarily introduce one degree in a neighbor of $S$ since the vertices of $S$ are non-adjacent. Therefore the net degree of $S$ and $N(S)$ must be equal.