0
$\begingroup$

Consider the graph below.

enter image description here

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is actually a really elaborate answer that follows closely with what I'm learning, and further explain's bof's answer at the same time. A quick question - For the independence number, is the idea to cover all the vertices with the sets of cliques? Also, what if the maximum degree of a vertex is higher than the maximum clique number? Are there any other obvious ways to show this? $\endgroup$ – Dewick47 Mar 30 '16 at 5:32
  • $\begingroup$ Yes, for the independence number, one way to show that $\alpha(G) \leq n$ is to partition the vertices into $n$ cliques. As for the max degree being higher than the max clique number, you can slightly generalise: if there does not exist $n$ vertices with degree at least $n-1$ then $\omega(G) < n$. Of course, you also need all $n$ such vertices to be adjacent to one another, so if no such set exists, then you can also conclude $\omega(G) < n$. $\endgroup$ – abc Mar 30 '16 at 5:47
  • $\begingroup$ Fantastic. Thank you for the wonderful explanation on these concepts. $\endgroup$ – Dewick47 Mar 30 '16 at 5:50
  • $\begingroup$ Glad you found it helpful $\endgroup$ – abc Mar 30 '16 at 13:47
3
$\begingroup$

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\},\ \{3,8\},$ and $\{3,5,6,9\}.$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I am assuming that the maximal degree of any vertex was just found visually? $\endgroup$ – Dewick47 Mar 30 '16 at 5:14
  • $\begingroup$ Yes. If you have a description or characterisation of the graph other than this picture, it would be useful to include it. $\endgroup$ – Servaes Mar 30 '16 at 5:16
  • $\begingroup$ This picture was the only information given. I needed to find both the independence number and the clique number, and justify those numbers. Also, did you mean the vertices $3, 5, 6, 9$? 4 is not adjacent to 9 or 3. $\endgroup$ – Dewick47 Mar 30 '16 at 5:18
  • $\begingroup$ @dewick49 Thank you for the correction, I misread. If the picture is all you have, then necessarily all your findings are found visually. $\endgroup$ – Servaes Mar 30 '16 at 5:27

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.