# Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$

Given graph $$G=(V,E)$$ and weight function $$w\,:\,E\to\mathbb{N}$$, function $$f(G,w)$$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges.

I want to prove that there is a Turing machine $$M$$ so I will get $$L(M)=CLIQUE$$, using function $$f$$, where $$CLIQUE$$ is the language of all $$(G,k)$$ so $$G$$ has a clique of size $$k$$.

I wrote the following algorithm:

$$M$$ on $$(G,k)$$:

1. Build a weight function $$w$$ so each edge in $$G$$ gets $$1$$.
2. Calculate $$f(G,w)$$.
3. Accepts if and only if $$f(G,w)\geq k$$.

My professor noted that it should be $$f(G,w)\geq {k \choose 2}$$. Is it possible to explain why?

A clique $$C$$ on $$k$$ vertices has $$\binom{k}{2}$$ edges, i.e., all unordered pairs $$\{a,b\}$$ such that $$a$$ and $$b$$ are distinct vertices in $$C$$.

The number of such pairs is $$\frac{k (k-1)}{2} = \binom{k}{2}$$. You can count these by focusing on the number of ordered pairs first. To make an ordered pair $$(a,b)$$ you have $$k$$ choices for $$a$$ and $$k-1$$ choice for $$b$$ (i.e., all vertices in $$C$$ except for $$a$$). The number of ordered pairs is then $$k(k-1)$$. To get the number of unordered pairs you only need to divide the above quantity by $$2$$ since, for each unordered pair $$\{a,b\}$$, we counted both $$(a,b)$$ and $$(b,a)$$.