# Is finding the largest subgraph in a graph where every vertex in the subgraph is connected to every other vertex NP-Complete

Is there a way to find the largest subgraph in a graph where every vertex in the subgraph is connected to every other vertex in the subgraph? Or is such a problem NP-Complete?

In math: $G = (V,E),$ $S \subseteq G$ s.t. $\forall$ vertices $u,v$ in the vertex set of S there exists an edge $e$ for $\{u,v\}$ and S is the largest such set.

I thought that it wasn't because you could start at a node then search through its neighbors in a breadth first manner. Then check that previously visited nodes are all part of the node's neighbors and passing the number of vertices in the constructed graph so far. After execution ends you should have the largest subgraph made for that vertex and then you repeat for the other vertices.

Would this algorithm work in answering the question or am I missing something?

INSTANCE: Let $G$ be a graph and let $x \leq |G|$ be an integer.
DECISION: Does $G$ contain a subgraph isomorphic to $K_{x}$?
This is NP-Complete. The optimization variant (finding the largest $x$) is NP-Hard.