Considering the following decision problems:
E_CLIQUE(G, k), where G = (V, E) is a simple graph and k >= 1 an integer. Does G have a clique of size 2 · k?
and
CLIQUE(G, l), where G = (V, E) is a simple graph and l ≥ 1 an integer. Does G have a clique of size l?
I am looking to prove that CLIQUE <=P E_CLIQUE, where <=P is a karp reduction. Any help would be appreciated.
To clarify, a clique of size k would be defined as a complete subgraph of size k of some graph G.
Hint: Consider a graph transformation $G \to \widetilde{G}$ which turns $G$ into a graph identical to $G$ but with one extra node, which has edges to any other node in $G$.