Prove that a graph with $100$ vertices with each edge having degree at most $4$ contains an empty graph of order $20$.

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

You can use Caroi-Wei theorem. In graph $G$ there is an independent subgraph $H$ with at least $$\alpha (G)=\sum _{i=1}^{100}{1\over d_i+1} \geq 100\cdot {1\over 5} = 20$$ vertices