Clique number

The clique number is the size of the largest complete subgraph in a graph. In Combinatorics, it tells you the biggest set of vertices where every pair is connected by an edge.

What is the clique number?

The clique number in Combinatorics is the size of the largest clique in a graph, meaning the biggest group of vertices that are all pairwise connected. If a graph contains a triangle, a 4-vertex complete subgraph, and no 5-vertex complete subgraph, its clique number is 4.

A clique is just a complete subgraph, so every edge you could draw inside that selected set is actually there. That is why the clique number measures local density inside a graph, not just whether the graph has a lot of edges overall. Two graphs can have the same number of edges and very different clique numbers.

You can think of the clique number as asking, “How large can a fully connected cluster get inside this graph?” In a complete graph with n vertices, the answer is n, because the whole graph is one big clique. In a bipartite graph, the answer is at most 2, since vertices inside the same part are never adjacent, so you cannot build a triangle.

This term shows up naturally when you study special graph families. For complete graphs, the clique number is easy to read off. For bipartite graphs, it gives a quick structural check. For regular graphs, the clique number is not determined just by the degree, because a graph can be regular without having a large complete subgraph.

A common mistake is to confuse clique number with vertex degree or with the number of connected components. Degree looks at one vertex at a time, while clique number looks at the largest all-to-all-connected group anywhere in the graph. Also, a large clique number does not mean the whole graph is complete, only that one part of it is very tightly connected.

Why the clique number matters in COMBINATORICS

Clique number matters in Combinatorics because it gives you a clean way to describe how clustered a graph is. Once you know the largest complete subgraph, you can compare graphs that might look similar at first but behave very differently in structure.

It also shows up when you classify special graphs from topic 10.4. A complete graph has the largest possible clique number for its size, a bipartite graph has a very small clique number, and regular graphs can vary a lot. That makes clique number a useful feature when you are asked to identify graph type from a diagram or from a description.

In problem solving, clique number often appears as a hidden step rather than the whole problem. You might be asked to find the biggest group of mutually adjacent vertices, check whether a graph can contain a triangle or a K4, or explain why a certain graph cannot have a large complete subgraph because of how its edges are arranged.

It also connects to bigger graph ideas like clustering and optimization. In social network-style problems, a clique models a tightly connected group where everyone is directly linked to everyone else. In class, that might show up as a short-answer question about why a graph does or does not contain a complete subgraph of a given size.

How the clique number connects across the course

Complete Graph

A complete graph is the easiest place to see the clique number in action, because the entire graph is itself a clique. If a graph is complete on n vertices, then its clique number is n. This makes complete graphs the upper-end example you compare other graphs against when checking how large a complete subgraph can get.

Bipartite Graph

Bipartite graphs usually have very small clique numbers, which makes them a sharp contrast with complete graphs. Since vertices in the same part are not adjacent, you cannot form a triangle inside a bipartite graph. That means the clique number is at most 2, so any graph with a 3-clique is automatically not bipartite.

Regular Graph

Regular graphs have equal degree at every vertex, but that does not tell you the clique number by itself. A graph can be 3-regular and still have only small cliques, or it can contain a fairly large complete subgraph inside a regular structure. This is a good reminder that degree and clique size measure different things.

Petersen Graph

The Petersen Graph is a classic example where the clique number is small even though the graph has a very structured, interesting shape. It is often used in graph theory because it resists easy intuition. Looking at its clique number helps you see that a graph can be highly symmetric without containing a large complete subgraph.

Is the clique number on the COMBINATORICS exam?

A problem set question might show you a graph and ask for its clique number, or ask whether a given complete subgraph exists. You answer by looking for the largest set of vertices where every pair is connected, then checking whether adding one more vertex breaks completeness. If the graph is described as bipartite, you can often use that structure to rule out cliques larger than 2.

In a diagram-based quiz item, this term usually shows up as a quick structural scan: identify triangles, K4s, or larger fully connected groups, then compare them. If the graph is regular, do not assume the clique number is tied to the degree alone. You need to check the actual edge pattern, not just the vertex degrees.

The clique number vs complete graph

A complete graph is a whole graph where every pair of vertices is connected, while clique number is a number that describes the largest complete subgraph inside a graph. A graph can have clique number 3 without being complete, because only one triangle is present. If the entire graph is complete, then the clique number equals the total number of vertices.

Key things to remember about the clique number

• The clique number is the size of the largest complete subgraph in a graph.

• A clique measures a fully connected group of vertices, so every pair in that group has an edge between them.

• Complete graphs have clique number equal to their number of vertices, while bipartite graphs have clique number at most 2.

• Clique number is about the biggest tightly connected cluster, not about total edges or vertex degree alone.

• When you find a clique number, look for the largest triangle, K4, or bigger complete subgraph that actually fits in the graph.

Frequently asked questions about the clique number

What is clique number in Combinatorics?

The clique number is the size of the largest complete subgraph in a graph. In other words, it tells you the biggest set of vertices where every vertex is connected to every other vertex in that set. If you find a K4 inside a graph and nothing larger, the clique number is 4.

Is clique number the same as complete graph?

No. A complete graph is a type of graph, while clique number is a number you assign to a graph. If the whole graph is complete, then the clique number matches the number of vertices. But a graph can have a smaller clique number if only part of it is fully connected.

What is the clique number of a bipartite graph?

A bipartite graph has clique number at most 2. That is because vertices in the same part are never adjacent, so you cannot form a triangle. If the graph has at least one edge, its clique number is usually 2.

How do you find clique number from a graph diagram?

Look for the largest group of vertices that are all pairwise connected. Start with triangles, then check whether you can extend them to a K4 or larger without missing any edges. A common mistake is to count a dense-looking group as a clique even when one edge is missing.