In doing a problem from Graph Theory by West. In one question it asks you to find the maximum sized clique in the graph. I think it's 5 (using the top or bottom vertex). However in the solution manual it mentions that because the graph contains two points of degree 3 this is not possible. Is that correct? Can anyone explain why if so?
A clique of size five would have to include at least one of the vertices of degree three, simply because there are only six vertices in the graph. However, in a clique of size five, each vertex must have four neighbours within the clique. A vertex of degree three cannot fulfill this.