Vtyjkyuk

My question is not about how to prove this, but one of the properties used to prove it.

Let HALF-CLIQUE = encode(G) 

let m be the number of node in G and k be the size of some clique. 
The proof is based around the relationship between m and k.

The function to reduce Clique to Half-Click is defined as follows:

1) if k = m/2 output G

2) if k < m/2 
 a) let j = m - 2k
 b) add j nodes to G and connect them to all other nodes in G
 including each other and call this new graph H
 c) output H
3) if k > m/2
 a) let j = 2k -m
 b) add j nodes to G and connect them to all other nodes in G
 including each other and call this new graph H
 c) output H

My question is the mathematical relationship between j = m -2k or j = 2k - m

I was messing with it and came up with this:

m = |Q|; where Q is the set of all nodes in G
k = |S|; where S is a subset of the nodes in G 
j = m - 2k; j is the number of nodes to add to G to yield a new graph H
n = j + m = |H|; n is the number of nodes in the new graph H 

I then flipped the formulas around a little in this way.

n = j + m
j = n - m
sub j into j = m - 2k
n - m = m - 2k
n = 2(m - k)
n/2 = m - k

Are you asking why we add $j=m-2k$, respectively $j=2k-m$ vertices?

You have to ask yourself what is the purpose of such an reduction.
We want that the following relation holds: $$ textG has a k-clique Leftrightarrow textH has a half-clique.$$

Basically we need $j$ many new vertices to have a suitable relation between $k$ (for k-clique) and $fracn2$ (for half-clique). To construct such an $H$ one can use your algorithm in the first two cases but the case $k>fracm2$ is wrong. You should not add any edges to the new vertices. Lets look on the particular cases to understand the reasoning:

1. $k=fracm2$: here we clearly can leave the graph as $n=m$.


2. $k<fracm2$: as you computed we get $fracn2=m-k$ so if we find in the graph $H$ a half-clique, i.e. a clique of size $fracn2$ then we used in the worst case all of the $j$ new vertices. So this clique corresponds to a clique in G of size at least
   $$fracn2-j=(m-k)-j=m-k-m+2k=k.$$
   Which is exactly what we wanted.


3. $k>fracm2$: here we have $$fracn2=fracm+j2=fracm+2k-m2=k.$$ So if there is a half-clique it has size $k$. But we did not add any edges to the new vertices. So non of them can be included in this clique. Therefore this clique is also contained in $G$. It has again by the proper choice of $j$ exactly size $k$.

As a good exercise you can think about the other direction: If $H$ has not a half-clique, then there is no k-clique in $G$.

This together with my argument should clarify why we have chosen $j$ in this particular way. In addition you can draw some picture to understand what I explained, or do an example with a small graph.

Hope this answers your question and helps you to understand the procedure.