Proving a clique number and independence number?

Question

Consider the graph below.

It is clear to see that the independence number $\alpha(G) = 3$ and the clique number $\omega(G) = 4$.

However, I need to prove this. The only method I know this far is that we could consider the clique number 5, which means the graph would require at minimum 10 edges. In this graph however, that is true...so I need a different way to prove that the clique number HAS to be 4, and the independence number HAS to be 3.

Does anyone have any tips or tricks on typical ways to prove a discovered clique or independence number?

Answer 1

In general, to show that $\omega (G) = n$, you need to show 2 things: firstly, there exists a clique with $n$ vertices, and secondly there is not clique with $n+1$ vertices. Here, it is firstly easy to find the clique comprising 4 vertices (so $\omega(G) \geq 4$). Secondly, a clique comprising 5 vertices cannot exist because there is no vertex with degree 5 (among any number of other reasons).

Dealing with the independence number is similar. To prove $\alpha(G) = n$, you need to show that there exists an independent set of vertices of cardinality $n$, and there is not independent set of vertices of cardinality $n+1$. The first part is easier: you construct the set of $n$ independent vertices and you are done (for our case, $\{ 7,4,3 \}$ will do). For the second part, an elementary argument might go something like this: since $\{3,5,6,9\}$ is a clique, only one of these vertices can feature in an independent set. Similarly, only one of the clique $\{ 1,2,7 \}$ can feature, and only one of the clique $\{4,8\}$ can feature. Therefore any independent set can feature at most one vertex from 3 distinct sets, so can comprise at most 3 elements.

Answer 2

From the picture there are $4$ vertices of degree $3$, and $5$ vertices of degree $4$.

As the maximal degree is $4$, the clique number is at most $4$. The vertices $\{3,4,6,9\}$ form a $4$-clique, so the clique number is exactly $4$.

An independent set can contain at most $1$ vertex from this $4$-clique. If there exists an independent set of size $4$ then it has $3$ vertices among $\{1,2,4,7,8\}$. This set can contain at most $1$ vertex from each of the $3$-cliques $\{1,2,7\}$ and $\{1,7,8\}$, and hence it must contain $4$. Then the only available vertices remaining are $1$ and $7$, which do not yield and independent set. Hence the independence number is at most $3$. The subset $\{2,5,8\}$, for example, shows that the independence number is exactly $3$.

Answer 3

The clique number is at least $4$ because $\{3,5,6,9\}$ is a clique; it is at most $4$ because the graph is $4$-colorable, i.e., the vertices are covered by the four independent sets $\{1,3,4\},\ \{2,9\},\ \{5,7\},\ \{6,8\}.$

The independence number is at least $3$ because $\{2,5,8\}$ is an independent set; it is at most $3$ because the vertices are covered by the three cliques $\{1,2,7\},\ \{4,8\},$ and $\{3,5,6,9\}.$