Graph Theory: Definition, Key Concepts, Types of Graphs, and Real-World Applications

Key takeaways

• Graph theory is the study of graphs, which consist of dots connected by lines.

• The purpose of graph theory is to organize and analyze relationships so you can solve problems involving networks, routes, and connected systems.

• A tree in graph theory is a connected graph with no cycles, meaning exactly one path connects any two vertices.

Graph theory dates back to 1735 when Leonhard Euler solved the Seven Bridges of Königsberg problem, laying the foundation for the field. Learn about the core concepts of graph theory, explore common graph structures, and discover how graph theory applies to real-world problems.

To start building your analytical skills, consider enrolling in the Fractal Data Science Professional Certificate. In as little as five months, you can learn to create compelling data stories to influence your audience and master the art of critically analyzing data while making decisions and recommendations.

What is graph theory?

Graph theory is a branch of mathematics that focuses on how data points connect. In this case, a “graph” is a network model of nodes (vertices or points) and lines (edges or links), representing connections between different entities. Each node represents a data point, whether a person, a value, or a piece of information, and the line shows the relationship between the points.

By using a network model, you can:

• Identify which data points have the most connections, how the strengths of these connections vary, and which points are the most isolated.

• Model almost anything that involves links as graph networks, such as social networks, neural networks, and bonds in chemistry, which is why this type of model is so useful across fields.

Read more: Unraveling Neural Network Models: A Comprehensive Guide

Who is the founder of graph theory?

Leonhard Euler founded graph theory in 1735. He was working on a famous puzzle related to the city of Königsberg, which has seven bridges crossing a river flowing alongside an island. He proved that it was impossible to take a walk that crossed every bridge exactly once, which led to the origin of what is now known as graph theory.

What is the purpose of graph theory?

Graph theory provides a flexible model for analyzing relationships, enabling decisions about routing, clustering, and network resilience. It allows you to take messy, real-world situations and organize them into points and lines.

Once you’ve characterized your network, you can ask questions like:

• What is the shortest way to get from one point to another?

• Which items group closely together?

• Which single connection, if removed, would split the network apart?

In real-life situations, these answers help you make decisions. For example, navigation applications use network models to find the shortest route from Point A to Point B, and social media sites use network models to understand how people connect.

Basic graph theory concepts

Learning the foundational vocabulary related to graph theory can help you put different concepts together to understand the system. The key concepts to start with include:

• Vertices and edges: A graph consists of a finite number of vertices connected by a set of edges. Each edge connects two vertices known as its endpoints. An edge may also connect a vertex to itself, in which case both endpoints are the same vertex.

• Degree of a vertex: The total number of edges connected to the vertex. A vertex with a high degree is well connected, and one with a degree of zero isn’t connected to anything.

• A path: The route from one vertex to another. If you can trace the connections from Point A to Point B, you’ve found the path.

• A cycle: A path that loops back to the starting point without repeating any edges.

• Connected and disconnected graphs: A connected graph allows you to reach every vertex from every other vertex, while a disconnected graph includes some dots cut off from the rest.

Types of graphs

Depending on how vertices connect with edges, graphs can take several forms, including simple graphs, multigraphs, weighted graphs, directed graphs, undirected graphs, and trees. Explore what makes each unique below.

• Simple graphs: The most basic type of graph; each pair of vertices connects to one or zero edges, and no vertex has an edge looping back to itself.

• Multigraphs: With this type of graph, more than one edge can connect the same two vertices. An extension of this is the pseudograph, which allows a vertex to have a relationship with itself.

• Weighted graphs: Weighted graphs add a number to each edge, called a weight, to show the strength of the connection.

• Directed graphs and undirected graphs: Directed graphs (also called digraphs) have arrows for edges showing a one-way relationship between points, while undirected graphs don’t show a direction and instead consider both points to be connected equally.

• Trees: A tree is a connected graph that connects every vertex without creating any loops.

Famous graph theory problems

A few famous graph theory problems include the Seven Bridges of Königsberg by Euler; the Four Color Theorem, which asks whether any map can use just four colors in a way where neighboring regions never share a color (spoiler: yes); and the Traveling Salesman Problem, which asks for the shortest route to visit a set of cities and return home.

What are the real-world applications of graph theory?

Professionals use graphical representations to show connections across industries. Some examples are:

• Social networking, in which platforms represent users as vertices and their connections as edges. This helps the algorithm to suggest new friends, spot communities, and determine the influence of different users.

• In computer science applications, graph models show computer networks and can represent the entire web as a giant graph of links pointing to one another.

• Biologists and ecologists also rely on graph theory. For example, graphs can describe food webs showing which species eat which, model how proteins interact with cells, and show neural connections within the brain.

• Another common application is in transportation and routing. Road maps become weighted graphs so that navigation and delivery companies can find the fastest or cheapest route within cities.

Build your career skills on Coursera

Planning to level up your analytical skills? Subscribe to our LinkedIn newsletter, Career Chat, to get weekly updates on popular tools and certifications. Or check out the following resources to keep learning:

• Hear from an insider: Meet the Data Analyst Using His Creativity to Tell Visual Stories

• Structure your learning: Data Science Learning Roadmap: Beginner to Expert

• Build your foundation: Data Analysis Terminology

Whether you want to develop a new skill, get comfortable with an in-demand technology, or advance your abilities, keep growing with a Coursera Plus subscription. You’ll get access to over 10,000 flexible courses.

Build job-ready skills with Coursera Plus

Start 7-day free trial

• 
• 
• 
• 

Start 7-day free trial