Prove that for every undirected graph $G$ of 100 vertices, if every vertex has degree at most $4$, then there exists a subset $S$ of 20 vertices such that no two vertices in $S$ are neighbors of one another.

I found this problem in the book Introduction to Theoretical Computer Science by Boaz Barak.

Here's my work:

We denote $e(G)$ to be the set of edges in a graph $G$ and $v(G)$ to be the set of vertices. Suppose for contradiction that there exists a graph $G$ such that $|v(G)| = 100$ and for all subsets of $v(G')\subset v(G)$ with $|v(G')|=20$ there exists a nonempty subgraph $G'$ with vertex set $v(G')$.

Since every vertex has degree at most $4$, we have $|E|\leq \frac{4\times 100}{2} = 200$. Then

$$\sum_{\substack{G'\subset G \\ |v(G')| = 20}}|e(G')| \geq \binom{100}{20}.$$ In summing the number of edges over all subgraphs of $G$ of size 20, it is also equivalent to counting each edge $\binom{98}{18}$ times. Then since $$\sum_{e\in e(G)}\binom{98}{18} = \binom{98}{18}|e(G)|=\sum_{\substack{G'\subset G \\ |v(G')| = 20}}|e(G')|,$$ it follows that $\binom{98}{18} 200 \geq \binom{100}{20}$.

I'm not sure how to get a contradiction from here.

Thanks in advance for any help.


I do not quite think that your approach can provide a contradiction.

A set of vertices, no two of which are joined to each other, is called an independent set. I will use this terminology. So our question is this : in a graph with hundred vertices and maximum degree four, we can find an independent set of size $20$.

Here's a better and easier way to do things. We will provide an algorithm that will find an independent set of size $20$ within the setup. Start with an empty set $S$.

  • Take any vertex $v$ in the graph, and add it to $S$.

  • Remove $v$ and its neighbours from the graph, and repeat the above step with the new graph.

  • End when there are no vertices left.

Now, what is the size of $S$? Note that at each step, at most five vertices removed at each step,since you remove the chosen vertex $v$ and its neighbours, of which there can't be more than four. Now, there are hundred vertices, which means that the steps given above repeat at least $20$ times. For each step, some new vertex is added to $S$. It follows that $S$ has at least $20$ elements.

Now, $S$ is an independent set. To see this, if two vertices $A$ and $B$ are in $S$ and are connected by an edge, then if (without loss of generality) $A$ was chosen before $B$ as a member of $S$ by the algorithm, then $B$ would have been removed from the graph, so it cannot have been made a member of $S$.

Consequently, $S$ is an independent set of size $20$.

Use the above approach for a generalization :

In every graph with $v$ vertices and maximum degree $d$, one can find an independent set of size $\frac n{d+1}$.

I am not sure that one can improve the number $\frac n{d+1}$. You can test this by trying trivial examples.

  • $\begingroup$ More concisely: Let $S$ be a maximal independent set of size $s.$ Since each vertex not in $S$ is adjacent to a vertex in $S,$ there are at least $n-s$ edges with one endpoint in $S,$ whence $n-s\le ks.$ $\endgroup$ – bof May 29 '18 at 3:09
  • $\begingroup$ Alternatively: By Turán's theorem, a graph on $100$ vertices with no independent set of size $20$ needs at least $215$ edges; but a graph on $100$ vertices with maximum degree $4$ has at most $200$ edges. $\endgroup$ – bof May 29 '18 at 3:21

You can also think in this way:

Choose an arbitrary vertex, say A. it can be adjacent to at most 4 vertex, so there are 96 vertex that is not adjacent, hence choose a vertex, say B, from that 96 vertex, and apply the same logic to vertex B. It is at most adjacent to 4 vertex, none of which is A, and not adjacent to 96;however, this 96 vertex might contain the-at-most-4-vertex that A is adjacent, so we cannot choose those definitely. Moreover, we already come from A, so we are left with 91 vertex. Hence choose another vertex, say C, and apply the same logic.

If you noticed, with every vertex we are left with 5 less vertex that is available to choose for the next vertex for our empty graph.Therefore, even in the worst case, we should have an empty graph of order 20.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.