3
$\begingroup$

If the graph was regular, that would be easy to show it. Choose one vertix from $300$, then there are $300-1-2=300-1\cdot3=297$ vertices that are not chosen and non-adjacent to chosen ones. Choose one from $297$, then there are at least $300-2-2\cdot2=300-2\cdot3$ vertices that are not chosen and non-adjacent to chosen ones, etc. When we have chosen the $99$-th vertices, there are at least $300-99-99\cdot2=300-99\cdot3=3$ vertices that are not chosen and non-adjacent to chosen ones, choose the last one from them. If the graph it's not regular, I think, we should choose the vertix that has the smallest degree in the induced subgraph whose vertex set is the set of vertices that are not chosen and not adjacent to chosen ones. But it doesn't help me to show that we can always do it (that this set is not empty on any of our 100 steps of choosing.

$\endgroup$
3
  • 2
    $\begingroup$ If the graph is not regular, then at every one of your steps there are more available vertices that are not pairwise edge-adjacent. $\endgroup$ May 27, 2021 at 1:10
  • $\begingroup$ If the graph is regular then it is made up of cycles, so it is even easier, and you only get equality when the cycles are all triangles. $\endgroup$
    – Asinomás
    May 27, 2021 at 1:45
  • $\begingroup$ Oh yeah, so it's just caro wei and concavity of $\frac{1}{x}$ with jensen. $\endgroup$
    – Asinomás
    May 27, 2021 at 2:45

1 Answer 1

2
$\begingroup$

Do the following: If there remains a vertex $v$ of degree at least 3, remove this vertex $v$ from $G$ and reset $G \leftarrow G \setminus \{v\}$. So for every 1 vertex removed there are at least 3 edges removed. So when we are done with this step, the resulting graph $G$ will have, for some integer $m$, maximum degree 2, and so every component of $G$ is a path or cycle. Furthermore, for some integer $m$, the graph $G$ will have $300-m$ vertices and no more than $300-3m$ edges.

So the existence of an independent set of 100 vertices in this resulting graph $G$ suffices for us. So to this end, let $U$ denote the set of vertices in a cycle of $G$ and let $W$ denote the vertices of $G$ that are each in a component of $G$ that is a path. Then there is an independent set $I$ of $G$ of size satisfying $$|I| \ge \frac{|U|}{3}+\frac{|W|}{2}.$$ [Indeed take the largest independent set of each component $C$ of $G$, if $C$ is a cycle then at least $ \left\lfloor \frac{|C|}{2}\right\rfloor \ge \frac{|C|}{3}$ vertices can be taken from $C$, if $C$ is a path then at least $\left\lceil \frac{|C|}{2}\right\rceil$ vertices from $C$ can be taken from $C$. The worst case is if every vertex in $U$ is in a triangle, and every vertex in $W$ is in a path of even length.] Furthermore, the constraint $|U|+|W|=300-m$ also holds. This lower bound for $|I|$ is minimized when $|W|$ is as small as possible. But that $G$ has at least $2m$ more vertices than edges implies $|W|\ge 2m$, and even with $|W|=2m$, this implies $$|I| \ge \frac{(300-m)-2m}{3}+m =100.$$ So indeed there is an independent set $I$ with at least 100 vertices and the result follows.


Another way to do this: This time remove all vertices of degree-2 or higher [instead of degree-3 or higher]. What will result is that $G$ is, for some integer $m$, a matching + isolated vertices with $300-m$ vertices and $300-2m$ edges.

So on the one hand, as $G$ is a matching, there is an independent set that contains each isolated vertex and exactly one vertex in each edge in $G$. So $G$ has an independent set of size at least $|V(G)|-|E(G)| \ge 300-m - (300-2m) = m$. On the other hand, $G$ has an independent set that is at least half of the vertices of $G$. So $G$ has an independent set of size at least $\frac{300-m}{2}$.

So $G$ has an independent set of size at least $\max\{\frac{300-m}{2}, m\}$. One can check that $\max\{\frac{300-m}{2}, m\}$ is at least 100 however, and so the result follows.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .