the clique problem
Picture a social network where an edge means two people are friends. A clique is a group in which EVERYONE is friends with everyone else: a perfectly connected clump, no missing friendships. The clique problem asks a yes/no question about a graph: is there a clique of at least a given size k? It is the prototypical 'find a fully mutually-connected group' problem.
Formally, in an undirected graph G a clique is a set of vertices such that every pair of them is joined by an edge. The decision problem CLIQUE takes a graph G and a number k and asks whether G contains a clique of size k. It is in NP: a candidate set of k vertices is a certificate, and a verifier checks in polynomial time that all k-choose-2 pairs are edges. Finding a large clique, however, seems to require searching among exponentially many vertex subsets, with no shortcut known.
CLIQUE is NP-complete, shown by a clean reduction from 3-SAT. From a 3-CNF formula with m clauses you build a graph with one vertex per literal-occurrence, grouped into m clusters of three. You connect two vertices by an edge whenever they are in DIFFERENT clauses AND are not contradictory (not a variable and its own negation). Then the formula is satisfiable if and only if this graph has a clique of size m, one consistent true literal picked from each clause. CLIQUE is also tightly bound to two siblings: a clique in G is exactly an independent set in the complement graph, and its complement vertices form a vertex cover, so the three problems reduce to one another almost for free.
In a graph on vertices {1,2,3,4} with edges 1-2, 2-3, 1-3, 3-4, the set {1,2,3} is a clique of size 3: all three pairs 1-2, 2-3, 1-3 are edges. There is no clique of size 4, since 1-4 and 2-4 are missing. So 'clique of size 3?' is yes, 'size 4?' is no.
CLIQUE: is there a set of k mutually-adjacent vertices? In NP (the set is the certificate) and NP-complete via 3-SAT.
Finding the MAXIMUM clique is NP-hard, but CLIQUE for a FIXED small k is in P (try all k-subsets, polynomially many). NP-completeness needs k to be part of the input.