Clique

A clique is a set of vertices in a graph where every pair of vertices is adjacent, so the set forms a complete subgraph. In Combinatorics, cliques show up in graph theory and Ramsey Theory problems.

What is clique?

A clique in Combinatorics is a group of vertices in a graph where every two different vertices are connected by an edge. That means the vertices inside the group form a complete subgraph, so the graph looks fully connected within that smaller set.

The size of a clique is just how many vertices are in it. A single vertex is technically a clique, and a pair of connected vertices is also a clique. When people talk about cliques in class, though, they usually mean a larger fully connected set that you can spot inside a bigger graph.

Here is the part that trips people up: a clique does not have to be the whole graph. The graph can have lots of missing edges overall and still contain a clique somewhere inside it. For example, a graph on six vertices might not be complete, but if three of those vertices are all connected to one another, those three form a 3-clique.

You will also hear about maximal cliques. A maximal clique is one you cannot expand by adding another nearby vertex without breaking the “every pair is connected” rule. Maximal does not mean largest possible, just that you cannot make it bigger in that graph. That is different from a maximum clique, which is the largest clique in the graph.

In Ramsey theory, cliques are one of the main structures we try to force or find. The big idea is that if a graph is large enough, some highly organized pattern must appear, and cliques are the cleanest example of that order. This is why clique language shows up in Ramsey numbers, complete graphs, and problems about guaranteed substructures.

A quick example makes the definition easier to see. If four vertices all connect to each other, that set is a 4-clique and forms a K4 inside the graph. If just one edge is missing, the set stops being a clique, because a clique requires every pair, not most pairs.

Why clique matters in COMBINATORICS

Clique is one of the main building blocks for graph problems in Combinatorics because it turns a messy network into a question about guaranteed structure. Once you can identify cliques, you can talk about complete subgraphs, compare different graph shapes, and measure how much order is hiding inside a graph.

This term matters most in Ramsey Theory. Ramsey questions often ask when a graph must contain a clique of a certain size, no matter how the edges are arranged. That gives you a concrete target inside a problem that otherwise feels open-ended: look for a fully connected group, then use the graph size or coloring setup to argue that it has to exist.

Cliques also connect to proof strategy. If you are asked to show that a certain graph contains a K3, K4, or larger complete subgraph, you are really being asked to check which vertices are mutually adjacent and whether any subset can be extended. That makes clique problems a mix of careful edge checking and structural reasoning.

The idea also shows up in applications like social networks, where a clique can model a tightly connected group. In class, that kind of example helps you translate abstract graph language into a real network, but the math stays the same: every pair in the set has to be linked.

How clique connects across the course

Complete Graph

A complete graph is the whole graph version of a clique. If every vertex in the graph is connected to every other vertex, then the graph itself is complete, usually written K_n. A clique is the same pattern, but only for a chosen subset of vertices inside a larger graph.

Ramsey Theory

Clique is one of the main objects Ramsey Theory tries to force. Ramsey problems ask when a graph must contain a complete subgraph of a certain size, even if the graph was built with no obvious order. That is why clique language appears so often in statements about unavoidable structure.

Arrow Notation

Arrow notation is a compact way to state Ramsey-type results involving cliques. It writes down that a large enough graph or coloring must contain a monochromatic or complete substructure of a certain size. If you can read the arrows, you can translate the statement into a clique guarantee.

Graph

You cannot talk about a clique without a graph, because the definition depends on vertices and edges. Clique problems usually start by inspecting a graph, then checking which subsets of vertices are fully connected. The graph gives the setting, and the clique is the substructure you are trying to find.

Is clique on the COMBINATORICS exam?

A quiz or problem set question will usually show you a graph and ask whether a specific set of vertices is a clique, or ask you to find the largest clique you can spot. The move is simple: check every pair inside the set and make sure an edge is present for each pair.

You may also be asked to connect cliques to Ramsey Theory, especially in questions about unavoidable complete subgraphs. In those problems, you are not just naming a clique, you are using it as evidence that a graph has a certain forced pattern. If a prompt gives a complete graph notation like K4 or asks for a maximal clique, pay attention to whether the question wants a subgraph, the biggest one, or just any valid example.

On written work, a strong response usually names the vertices, verifies the pairwise connections, and states why the set qualifies. If the set fails, the missing edge is the reason. That kind of precise edge checking is the whole skill.

Clique vs Complete Graph

A clique is a fully connected subset of vertices inside a graph, while a complete graph is the entire graph when every vertex connects to every other vertex. So a clique can live inside a bigger graph that is not complete. If the whole graph itself is complete, then the entire vertex set is also a clique.

Key things to remember about clique

• A clique is a set of vertices where every pair is connected by an edge.

• Cliques form complete subgraphs, but they do not have to be the whole graph.

• A maximal clique cannot be made bigger without breaking the clique property.

• Clique language shows up a lot in Ramsey Theory because it describes forced order inside large graphs.

• To check a clique, look at every pair of vertices and make sure no edge is missing.

Frequently asked questions about clique

What is clique in Combinatorics?

A clique in Combinatorics is a set of vertices in a graph where every pair of vertices is adjacent. In other words, the vertices form a complete subgraph. The term is used a lot in graph theory and Ramsey Theory when you are looking for guaranteed fully connected patterns.

How do you tell if a set of vertices is a clique?

Check every pair of vertices in the set and make sure there is an edge between them. If even one pair is missing an edge, the set is not a clique. For a small set, this is just a careful edge check, but for larger graphs it can take a lot of bookkeeping.

What is the difference between a clique and a maximal clique?

A clique is any fully connected set of vertices. A maximal clique is a clique that cannot be extended by adding one more vertex while keeping every pair connected. Maximal does not mean biggest overall, just that it cannot grow any further in that graph.

Why do cliques matter in Ramsey Theory?

Ramsey Theory studies when order must appear in large enough structures, and cliques are a clean example of that order. Many Ramsey problems ask when a graph must contain a complete subgraph of a certain size. That makes cliques the pattern you are trying to force or identify.