2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$

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.