# Approximation factor for graph problems

I am attempting to figure out how to use approximation factors to determine the answers an algorithm can return for graph problems.

For example, if a graph G actually has a maximum clique with 13 vertices, and we use a 1.5-approximation algorithm to approximate the maximum clique - what is the minimum size clique that can be returned by this algorithm?

My first thought was to simply divide 13 / 1.5 since this would represent the worst that the algorithm could do. However, since that is ~ 8.6, would the minimum the algorithm returns be 9 or 8?

An approximation algorithm for a maximization algorithm has an approximation ratio of $\alpha \geq 1$ if whenever the true answer is $m$, the algorithm is promised to return a solution with value at least $m/\alpha$.
In your case, $m = 13$ and $\alpha = 1.5$, and so by definition, the algorithm must return a clique whose size is at least $13/1.5$. Since the size of the clique is an integer, if a clique is of size at least $13/1.5 \approx 8.6$, then it is in fact at least $\underline{\quad}$ (fill in the blanks).