Half-Clique ∈ NP by reduction from K-Clique. My question is not about how to prove this, but one of the properties used to prove it. 
Let HALF-CLIQUE = { encode(G) | G is a graph with a clique of at least half its nodes}

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

 A: 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: $$ \text{G has a k-clique} \Leftrightarrow \text{H has a half-clique}.$$
Basically we need $j$ many new vertices to have a suitable relation between $k$ (for k-clique) and $\frac{n}{2}$ (for half-clique). To construct such an $H$ one can use your algorithm in the first two cases but the case $k>\frac{m}{2}$ is wrong. You should not add any edges to the new vertices. Lets look on the particular cases to understand the reasoning:


*

*$k=\frac{m}{2}$: here we clearly can leave the graph as $n=m$.

*$k<\frac{m}{2}$: as you computed we get $\frac{n}{2}=m-k$ so if we find in the graph $H$ a half-clique, i.e. a clique of size $\frac{n}{2}$ 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
$$\frac{n}{2}-j=(m-k)-j=m-k-m+2k=k.$$
Which is exactly what we wanted.

*$k>\frac{m}{2}$: here we have $$\frac{n}{2}=\frac{m+j}{2}=\frac{m+2k-m}{2}=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.
