Which infinite graphs have finite clique number?

150 Views Asked by At

A graph I mean an undirected one. A complete subgraph of a graph $G$ is called a clique. A maximal clique is a clique which is maximal with respect to inclusion. The clique number of $G$, written as $\omega (G)$, is the maximum size of a clique in $G$. Clearly, a finite graph has finite clique number. But my question is that:

What properties imply that an infinite graph $G$ have a finite clique number?

1

There are 1 best solutions below

2
On BEST ANSWER

A graph has finite clique number if there exists some number $n$ such that for any $n$ vertices in the graph, at least two of them are not joined by an edge.

Therefore any graph with finite degree $d$ has finite clique number, less than or equal to $d+1$.

More generally, if the degree is infinite but for any integer $n$ larger than some bound $d$ there are less than $n$ vertices with degree $n-1$ or higher, then the clique number is finite and at most $d$.