We have a graph $G$ with $v$ vertices. In $G$ there is at least a maximum clique with $k$ vertices, with $k\lt v$. Is it true that there is at least a vertex of $G$ such that its degree is less than $k-1$?


1 Answer 1


The question is not clear. Is this the claim you are considering:

If the largest clique in a graph $G=\langle V,E\rangle$ is of size $k<|V|$, then there exists a vertex $v\in V$ of degree $d\leq k-1$.

If so then the claim is wrong. Let $d\geq 2$ and consider the full bipartite graph $K_{d,d}=\langle V,E\rangle$, where $V=L\cup R$ is a disjoint union of two sets of size $d$, and $E=\{ \{u,v\} : u\in R, v\in L\}$. Clearly, $K_{d,d}$ is $d$-regular, and the largest clique in it is of size $k=2\leq d$.

  • $\begingroup$ What I mean in the question is what you wrote. Your example is right, therefore the claim is wrong. Thank you for the answer. $\endgroup$ Aug 29, 2023 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.