I am trying to write an algorithm which will find all Cliques (complete subgraphs) in a graph. Each input vertex must be only in one resulting Clique. The algorithm must have O(N^2) time complexity. Each clique in the result must be as big as possible.

package main

import (
    "fmt"
)

type Vertex struct {
    Value int
}

type CompleteSubGraph struct {
    vertecies []Vertex
}

func areConnected(vertex1, vertex2 Vertex) bool {
    // 2 verteces are connected if their value sum is even
    return (vertex1.Value+vertex2.Value)%2 == 0
}

func (vertex1 Vertex) getConnectedVertices(vertices []Vertex, maxVertices int) (verticesConnectedWithVertex1 []Vertex) {
    for _, vertex2 := range vertices {
        if areConnected(vertex1, vertex2) {
            verticesConnectedWithVertex1 = append(verticesConnectedWithVertex1, vertex2)
        }
        if len(verticesConnectedWithVertex1) >= maxVertices {
            break
        }
    }
    return
}

func findAllCompleteSubGraphs(
    vertices []Vertex,
    maximumNumberOfVerticesForSubGraph int,
) (allCompleteSubgraphs []*CompleteSubGraph) {
    /*
       every vertex from input vertices
       must be only in one CompleteSubGraph

       the Algorithm must work not slower than O(N^2)
       where N is len(vertices)

       each vertex from input vertices must be only in one
       resulting CompleteSubGraph

       each CompleteSubGraph must be as big as possible
    */
    for _, vertex1 := range vertices {
        connectedToVertex1 := vertex1.getConnectedVertices(vertices,
            maximumNumberOfVerticesForSubGraph)
        fmt.Println("vertex", vertex1)
        fmt.Println("is connected to", connectedToVertex1)
    }
    return
}

func main() {
    vertices := []Vertex{
        Vertex{Value: 1}, Vertex{Value: 2}, Vertex{Value: 3},
        Vertex{Value: 4}, Vertex{Value: 5}, Vertex{Value: 6},
        Vertex{Value: 7}, Vertex{Value: 8}, Vertex{Value: 9},
        Vertex{Value: 10}, Vertex{Value: 11}, Vertex{Value: 12},
    }
    fmt.Println("result", findAllCompleteSubGraphs(vertices, 3))
}

I am checking if 2 vertecies are connected by an edge using areConnected function. It's simple just for example but will be more complicated in real life.

I have to use func (vertex1 Vertex) getConnectedVertices as it is defined now. I stuck on the cycle

        for _, vertex1 := range vertices {
            connectedToVertex1 := vertex1.getConnectedVertices(vertices,
                maximumNumberOfVerticesForSubGraph)
            fmt.Println("vertex", vertex1)
            fmt.Println("is connected to", connectedToVertex1)
        }

Can hardly imagine how to finish the algorithm. Will appriciate any advise.

Playground

Update

The original problem which I am trying to solve: Find groups of people who fit each other by some characteristics. AreConnected is true when person1 likes person2 and person2 likes person1. The task is to create groups of people with maximum size by a list of people. It is believed that big groups are better than small groups.

O(n^2) isn't enough time to enumerate all possible cliques in a graph, even if we (incredibly optimistically) assume O(1) processing time per clique. Consider an n-vertex graph consisting of n/3 disjoint triangles -- that is, n/3 sets of 3 vertices, with each vertex having edges to the other 2 vertices in its group and to no other vertices. Notice that you can independently choose a single vertex from each of the n/3 triangles to get an independent set (a set of n/3 vertices, no two of which are connected by an edge). Now invert all edges in this graph: this gives a graph in which the same choice of vertices now gives a clique of size n/3. There are 3^(n/3) cliques of this size, all of which are maximal (cannot have any vertices added to them and remain cliques). 3^(n/3) is much larger than n^2, so you cannot hope to even list all these cliques in O(n^2) time.