Dense graph

In mathematics, a dense graph is a special kind of graph where most pairs of points, or vertices, are connected by lines, or edges. Imagine a network where almost everyone is friends with everyone else—that’s what a dense graph looks like in math!

The idea of a dense graph is important because it helps mathematicians and computer scientists understand how information or relationships might flow in very well-connected systems. For example, in a dense graph, messages could travel quickly because there are so many paths to choose from.

The exact number of edges that makes a graph “dense” can vary depending on the situation. Sometimes a graph with more than half of the possible connections is called dense, while other times the bar is set higher. This flexibility means that experts define density in ways that best fit their specific problems.

Dense graphs are often studied to contrast them with their opposite—sparse graphs, which have very few connections. Understanding both types helps in many areas, from social networks to computer algorithms.

Graph density

In mathematics, a dense graph is one that has many connections, or edges, between its points, or vertices. Imagine you have a group of people, and each person can shake hands with everyone else just once. If almost everyone shakes hands, we call this a dense graph because it has almost the maximum possible connections.

The density of a graph measures how close it is to having the most possible edges. For a group of people, this would mean how many handshakes happened compared to the maximum possible. A complete graph, where everyone shakes hands with everyone else, has the highest density. On the other hand, a sparse graph has very few connections, like if only a few people shook hands.

Upper density

Upper density is a way to talk about how close an infinite graph is to having as many connections as possible. It helps us understand the maximum number of connections possible in very large graphs.

Using a special math rule called the Erdős–Stone theorem, we know that upper density can only be certain specific numbers, like 1 or fractions such as 1/2, 2/3, 3/4, and so on.

Sparse and tight graphs

Some graphs have very few edges compared to the number of vertices they contain. These are called sparse graphs. For example, trees — graphs where each vertex is connected in a way that there are no cycles — are a type of sparse graph.

There are special ways to describe how sparse a graph can be using numbers. For instance, a graph might have a certain maximum number of edges depending on how many vertices it has. Graphs that meet this exact maximum are called "tight" graphs. Different kinds of graphs, like planar graphs (graphs that can be drawn on a flat surface without lines crossing), can also be described this way.

Sparse and dense classes of graphs

Some mathematicians study groups of graphs instead of single graphs. They call a group of graphs "somewhere dense" if a certain rule applies — basically, if big connected graphs can be found inside smaller parts of graphs in the group. If this rule does not apply, the group is called "nowhere dense".

Certain groups of graphs, like those with limits on how their points connect, fall into a category called "biclique-free graphs". These groups do not include specific big connected graphs with two separate sets of points.