Graph Theory - Proof

Question

I am need help to Prove the following statement:

Let G be a $k$-regular graph with $n$ vertices and $k \geq 1$. Prove that $G$ does not have an independent set of size greater than $\dfrac{n}{2}$.

Much Appreciated!

Answer 1

I would prove this by contradiction. Suppose $G$ has an independent set $I$ such that $|I| \geq \dfrac{n}{2}$. Then none of the vertices in $I$ are adjacent by definition of an independent set. However, each vertex has degree at least $1$, so each vertex is adjacent to some other vertex. So each vertex in $\overline{I}$ can map to $k$ distinct vertices. This gives us at most $\dfrac{k(n-2)}{2}$ edges. By the handshake lemma, we need to satisfy $2E = 2kn$. And so, we must connect vertices in $I$ with edges, contradicting the definition of an independent set.

Answer 2

If the graph is $1$-regular, $n$ has to be even. We can partition the vertex set into pairs of vertices so that there is an edge between vertices in a partition. An independent set contains not more than one vertex from each partition. Hence, the size of a independent set cannot exceed $\frac{n}{2}$.

Let $G$ be a $k$-regular graph ($k$ is at least $2$) with $n$ vertices.

Case 1: $k>\frac{n}{2}$

Let $X$ be an independent set with more than $\frac{n}{2}$ vertices. There must be at least $k$ vertices (of $G$) that do not belong to $X$. But, $|X|+k>n$, a contradiction.

Case 2: $k\le \frac{n}{2}$

If $G$ contains an independent set of length $r$, then $G'$ (complement of $G$) contains a $r$-clique as a subgraph and vice versa. We show that $G'$ does not contain a $r$-clique where $r>\frac{n}{2}$. We need to have at least as many $E\left(T(n,\lceil \frac{n+1}{2}\rceil)\right)+1$ edges for a clique of size $\lceil \frac{n+1}{2}\rceil$ (where $T(n,k)$ stands for Turan graph of $n$ vertices and $k$ parts, $E(A)$ stands for number of edges in graph $A$). But, we have $\frac{n(n-k)}{2}\le \frac{n(n-2)}{2}$ edges. (We can use the estimate $E(T(n,m))\le \left( 1-\frac{1}{m} \right)\frac{n^2}{2}$ and carefully work out cases when $n$ is even and odd to prove the required inequality).