Complete graph

Imagine a group of dots. In a special group, every dot joins to every other dot. These lines make a web. Long ago, people drew these shapes. They called them mystic roses. One man named Ramon Llull drew them. They look like stars or flowers. Some shapes are flat. Others must have lines that cross.

If you have many dots, the lines will cross each other. It is a very busy web of lines!

Imagine a group of dots. In a complete graph, every dot connects to every other dot. These dots are called vertices. The lines between them are called edges. This makes a very busy web.

People have studied these shapes for a long time. In the 13th century, Ramon Llull drew them. He placed the dots on a regular shape. Some people call these drawings mystic roses.

Small complete graphs can stay flat on a page. We call these planar graphs. But things change as you add more dots. A complete graph with five or more dots must have crossing lines.

These shapes also help us understand 3D objects. For example, a triangle is a complete graph with three dots. A tetrahedron is also a complete graph. Some complex shapes, like the Császár polyhedron, use these graphs as a skeleton.

This special shape looks like a torus, which is a ring shape. Math helps us see how these dots and lines build our world.

Imagine a group of dots spread out on a page. In math, we call these dots vertices. Now, imagine drawing a line between every single pair of dots. This creates a very busy web where no dot is left out. This special pattern is called a complete graph. In this type of graph, every vertex has a direct connection to every other vertex. This makes the graph very strongly connected. It is hard to break the graph apart into separate pieces.

There are many ways to measure these busy webs. We use the symbol K to name them. The number after the K tells us how many dots are in the graph. For example, K4 has four dots. A complete graph with n dots has a specific number of edges. This number is called a triangular number. As you add more dots, the number of lines grows very quickly. If you have a complete graph with an even number of dots, you can find perfect matchings. These are sets of edges that connect every dot without sharing any lines.

People have been interested in these patterns for a very long time. In the 13th century, Ramon Llull made drawings of these shapes. He placed the dots on the corners of regular shapes. These beautiful drawings are sometimes called mystic roses.

Later, in 1736, Leonhard Euler began the field of graph theory. His work focused on the Seven Bridges of Königsberg. Some people think the letter K in our math notation honors Kazimierz Kuratowski. Other people think it might come from a German word.

Complete graphs also help us understand shapes in space. A triangle is a complete graph with three vertices. A tetrahedron is also a complete graph.

These shapes can even form the skeleton of 3D objects. The Császár polyhedron is a special shape that looks like a ring, or a torus. It uses a complete graph as its frame.

This shape is quite complex because it is not convex. It shows how simple dots and lines build big structures.

We can also look at how these graphs fit on a flat surface. Small complete graphs like K4 are planar. This means you can draw them without any lines crossing each other.

However, once you have five or more dots, things change. A complete graph with five or more vertices must have crossing lines.

This makes them nonplanar. Mathematicians use these crossing rules to study many different types of shapes and networks.

In the mathematical field of graph theory, a complete graph is a very specific type of network. It is defined as a simple undirected graph where every pair of distinct vertices is connected by a unique edge. A vertex is a single point, and an edge is the line connecting two points. In a complete graph, no two points are left unconnected. There is also a version called a complete digraph. This is a directed graph where every pair of distinct vertices is connected by a pair of unique edges. In this version, each edge has a specific direction, so there is one edge going from point A to point B, and another going from B to A.

We use a specific notation to identify these graphs. A complete graph with $n$ vertices is denoted by $K_n$. There is some debate about why the letter $K$ is used. Some sources suggest it stands for a German word. However, the German name for a complete graph does not actually contain the letter $K$. Other sources state that the notation honors Kazimierz Kuratowski, a person who made important contributions to graph theory. Regardless of the origin, this symbol allows mathematicians to quickly describe the size of the network.

Complete graphs have several unique mathematical properties. A graph with $n$ vertices will always have $n(n-1)/2$ edges. This number is known as a triangular number. Because every vertex connects to every other vertex, the graph is also a regular graph of degree $n-1$. This means every single point has the exact same number of lines coming out of it. These graphs are also considered maximal cliques. They are also maximally connected. The only way to disconnect the graph by removing vertices is to remove the entire set of vertices.

History shows that people have been drawing these patterns for centuries. While graph theory is often dated to Leonhard Euler's 1736 work on the Seven Bridges of Königsberg, complete graphs appeared much earlier. In the 13th century, Ramon Llull created drawings of complete graphs. He placed the vertices on the points of a regular polygon. These beautiful drawings are sometimes called mystic roses.

These graphs are deeply connected to geometry and topology. A complete graph with $n$ vertices serves as the edge graph of an $(n-1)$-dimensional simplex. For example, a triangle is a complete graph with three vertices. A tetrahedron is a complete graph with four vertices.

The Császár polyhedron is a fascinating example of this connection. It is a nonconvex polyhedron with the topology of a torus, which is a ring shape. This complex object uses a complete graph as its skeleton.

Mathematicians also study how these graphs can be drawn on flat surfaces. We call a graph planar if it can be drawn without any edges crossing. Small complete graphs like $K_3$ and $K_4$ are planar. However, any complete graph with five or more vertices is nonplanar. This means a planar drawing of $K_5$ or larger must contain at least one crossing. $K_5$ is a key part of Kuratowski's theorem. This theorem states that a graph is planar if and only if it does not contain a subdivision of $K_5$ or a complete bipartite graph.

In three-dimensional space, complete graphs can create even more complex structures. Conway and Gordon proved that every embedding of $K_6$ into three-dimensional space is intrinsically linked. This means there will always be at least one pair of linked triangles within the structure. They also showed that any three-dimensional embedding of $K_7$ contains a Hamiltonian cycle that forms a nontrivial knot. This demonstrates how simple connections between points can lead to intricate topological phenomena.