Graph theory

Dots can be joined by lines.

These dots are called vertices. The lines are called edges. Edges show how things connect.

Some lines have arrows. These show a direction. Other lines can have numbers. This is a weight. Some lines can even loop back.

A man named Euler studied bridges. He used these ideas to solve a puzzle. Math helps us see how things link together.

Imagine dots connected by lines.

In math, we call these dots vertices. The lines are called edges. These parts help us model how things relate to each other.

Some edges have arrows. We call these directed graphs. These arrows show a specific direction. Other graphs are undirected. This means the lines link things both ways. Some edges even have numbers. We call these weights.

Graph theory has a long history. Leonhard Euler wrote the first paper on this. He studied the Seven Bridges of Königsberg.

He wanted to see how the bridges linked the land.

Another famous puzzle is the four color problem. It asks if any map can be colored with only four colors. This rule means no two areas sharing a border have the same color. This problem took over a century to solve. In 1976, two men used computers to find the answer. They checked many different shapes to prove it works. Today, graphs help many people. They help chemists and engineers talk about how parts fit together.

Imagine a collection of dots connected by lines. In mathematics, this structure is called a graph. The dots are known as vertices, or sometimes nodes. The lines connecting them are called edges, or links.

Graphs are used to show how different objects relate to one another. Some graphs are undirected, meaning the edges work both ways. Other graphs are directed, which means the edges have arrows showing a specific direction.

Some graphs even have numbers on the edges, which are called weights.

There are many different ways to build these structures. A simple graph has edges that connect two different vertices. A multigraph is different because it can have many edges between the same two dots. It can also have a loop, which is an edge that connects a vertex to itself. Some graphs are mixed, meaning they have both directed and undirected edges. You can also study how many edges a graph has to find its crossing number.

This helps people plan things like factory tracks to avoid too many crossings.

Graph theory began with a famous puzzle about bridges. In 1736, Leonhard Euler published a paper about the Seven Bridges of Königsberg.

He wanted to understand how the bridges linked the different parts of the land. Later, in 1878, James Joseph Sylvester introduced the actual term "graph." In 1936, Dénes Kőnig wrote the very first textbook on the subject. By 1969, Frank Harary wrote a famous textbook that helped many different scientists talk to each other.

One of the most famous puzzles is the four color problem. It was first asked by Francis Guthrie in 1852. The problem asks if any map can be colored using only four colors. The rule is that no two areas sharing a border can have the same color. This was a hard job that took over a century to solve. In 1976, Kenneth Appel and Wolfgang Haken used computers to find a proof. They checked 1,936 different shapes to prove it worked.

Today, graph theory connects many different areas of science. It helps chemists understand how molecules are put together. It also helps electrical engineers study how current flows through circuits. Scientists use math to study the symmetry of graphs, which is called algebraic graph theory. Some graphs, like the Petersen graph, are very symmetrical.

These ideas help us understand everything from social networks to the way things are shaped in space.

Graph theory is a major branch of discrete mathematics. It focuses on the study of graphs. In this context, a graph is a mathematical structure. It is used to model pairwise relations between objects.

A graph consists of two main parts. The first part is a set of vertices, also called nodes or points. The second part is a set of edges, also called arcs, links, or lines. These edges connect the vertices together. The two vertices at the ends of an edge are called endpoints.

There are several different types of graphs. An undirected graph features edges that link two vertices symmetrically. In contrast, a directed graph has edges with a specific orientation. These edges are marked with arrows to show direction. A mixed graph contains both directed and undirected edges. Some graphs are considered simple graphs. A multigraph is more complex. It allows many edges to share the same pair of endpoints. It also allows for a loop, which is an edge connecting a vertex to itself.

Additionally, edges can be assigned a number. This number is known as a weight. A graph with these values is called a weight graph.

The history of graph theory began with a famous puzzle. In 1736, Leonhard Euler published a paper about the Seven Bridges of Königsberg.

This work is considered the first paper in the history of graph theory. The term "graph" was later introduced by James Joseph Sylvester in 1878. In 1936, Dénes Kőnig wrote the first textbook on the subject. Later, Frank Harary published a definitive textbook in 1969. This book helped mathematicians, chemists, and engineers communicate.

Graph theory also grew from the study of topology and modern algebra.

A famous challenge in this field is the four color problem. Francis Guthrie first posed this problem in 1852. It asks if any map can be colored with only four colors. The rule is that no two regions with a common border can share a color. Many people tried to prove this for many years. In 1969, Heinrich Heesch suggested using computers to solve it. In 1976, Kenneth Appel and Wolfgang Haken produced a computer-aided proof. They checked 1,936 specific configurations to reach their conclusion.

A simpler proof was later found using only 633 configurations.

Topological graph theory is a specialized subarea. It treats graphs as topological spaces. This field studies how graphs can be embedded in surfaces. An embedding represents a graph where vertices are points and edges are arcs. In a proper embedding, edges do not intersect except at their endpoints. This field also looks at the crossing number. The crossing number is the minimum number of edge crossings in a graph. This concept was inspired by Pál Turán. He studied how to minimize crossings between tracks in a factory plan.

Algebraic graph theory uses algebra to study graphs. It often uses branches like linear algebra and group theory. Spectral graph theory is a specific type of this study. It focuses on the adjacency matrix of a graph. This matrix represents the graph using numbers. Scientists also look at the Laplacian matrix. This involves the degree matrix and the adjacency matrix. Another area is the study of symmetry. Some graphs are highly symmetrical, such as the Petersen graph.

This graph is known for being vertex-transitive and distance-regular.

Graph theory connects to many other scientific fields. In chemistry, it helps describe molecular composition. In physics, it relates to electrical circuits. Gustav Kirchhoff used graph-like techniques in 1845 to study voltage and current. Geometric graph theory also plays a role. It studies the properties of graphs drawn in Euclidean space. This includes the study of planar straight-line graphs. These are graphs where edges are non-crossing line segments. Today, graph theory remains a vital tool for understanding complex systems.