I was wondering if somebody could help me with a graph-related proof!
Let:
- $G=(V,E)$ be an undirected graph;
- $S \subseteq V$ a maximal independent set;
- $\Delta$ the maximum degree of the graph ( = the maximum number of edges any vertex has).
I strongly suspect that $\Delta \geq \frac{|S|}{|V \setminus S|}$ for a certain category of graphs, like non-trivial connected graphs perhaps; however I'm struggling to prove it and yielded poor results so far.
What do you guys think, can this be (dis)proved?
Yes, this is true for all connected graphs on more than $1$ vertex. (Or, for an even weaker assumption, all graphs with no isolated vertices.)
Let $S$ be a maximal independent set. Each vertex of $S$ must be adjacent to some vertex of $V \setminus S$, since otherwise it wouldn't be connected to anything.
This gives us at least $|S|$ edges incident to $|V\setminus S|$ vertices, so one of the vertices must be incident to at least $\frac{|S|}{|V\setminus S|}$ of them.