A complete graph is an undirected graph where each vertex is connected to every

other vertex by an edge. Consider a complete graph

$$

$=$

$($

$$

$,$

$$

$)$

$$with

$$

$$vertices$,$ where an edge

weight

$$

$$

$$is defined on each edge. As additional input, you are given two positive integers

$$

and

$$

$.$

$$Consider the following problem: given these inputs, is there a set of vertices of size

$$

$$such that for each pair of vertices in this set, the edge connecting them has weight at least

$$

$?$

$($

a

$)$

$[$

$2$

$$points

$]$

$$Draw an example of this problem where the answer is true

$($

and describe your

solution

$)$

$.$

$($

b

$)$

$$Draw an example of this problem where the answer is false

$($

and briefly explain

why there is no solution

$)$

$.$

$($

c

$)$

$$Prove that the original problem is NP

$-$

complete using $3-$SAT