liveBook · Manning

Complete subgraph

As explained in Algorithms Every Programmer Should Know

A complete subgraph is a subgraph in which every pair of distinct vertices is connected by an edge.

A complete subgraph, or clique, is a group of vertices in an undirected graph where every distinct pair is joined by a direct edge. One missing edge is enough to disqualify the group. section 11.1 section 11.4

A maximal clique is a complete subgraph that cannot be enlarged without losing that property. A clique need not be maximal: a smaller complete group may be part of a larger one. section 11.1

Figure 11.1 The left diagram shows every one of the five vertices connects directly to all 4 others, so all possible 10 edges are present, making it a clique. On the other side, we have a missing edge from vertex 2 to 3, which is enough to disqualify the whole group, so it is not a valid clique.

Compare a five-vertex group with all ten possible edges to one missing just the edge between vertices 2 and 3; only the first is complete. section 11.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines completeness and distinguishes maximal cliques, then uses the distinction in an algorithm walkthrough.
Examples
Uses a five-vertex graph and a trust-circle scenario to illustrate mutual connections and a disqualifying missing edge.
What you can do after
Understand how to distinguish a complete subgraph from a maximal clique.
How it connects
Connects cliques to undirected graphs, maximal cliques, and the Bron–Kerbosch algorithm.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.