By taking the complement graph, i.e., replacing $E$ with $E'$ where $e \in E'$ iff $e \not\in E$, we get the related problem: Let $G = (V,E)$ be a graph. Can $V$ be partitioned into two non-empty parts such that $V1$ and $V2$ are independent sets?
This problem is then actually equivalent to asking whether $(V,E)$ is a bipartite graph. An approach to solve this could be the following:
- Color all vertices gray.
- Choose some initial vertex $v_0$ and color it white.
- If there are no more gray vertices, the graph is bi-partitie, as witnessed
by its coloring.
- If some white vertex has a white neighbour, the graph is not bipartite.
- Color all gray vertices with a white neighbour black.
- If some black vertex has a black neighbour, the graph is not bipartite.
- Color all gray vertices with a black neighbour white.
- Go to step 4.
Changing this to an algorithm for 2-Clique is straightforward, and it is easy to show that this algorithm runs in polynomial time.
Edit: The algorithm as stated deals only with the case where $(V,E)$ is connected. For non-connected graphs, add a step 7.5: If, in the last round of the algorithm, no vertex got a new color (i.e., in line 5 and 7, no change occured), choose any gray vertex and color it black or white.
A good choice of coloring strategy for the original problem is easy to find and left as an exercise to the reader :).