What is a Graph?

What exactly is a Graph?

A graph is not a chart or a plot with x and y axes that you might have seen in your math class. In graph theory, a graph is a mathematical structure that represents relationships between objects. It’s one of the most versatile and powerful concepts in mathematics and computer science.

Think about it: Nearly everything around us involves connections and relationships. Your social network, the roads between cities, the links between web pages, the neurons in your brain—all of these can be represented as graphs!

The Building Blocks: Vertices and Edges

In mathematics, a graph is an abstract structure used to model relationships between objects. It consists of two primary components:

• Vertices (also called nodes or points): These are the fundamental entities or objects within the graph. Think of them as dots or circles in a diagram.

• Edges (also called links, arcs, or connections): These are the lines that connect pairs of vertices, representing the relationship between them.

Formal Definition

Formally, a graph $G$ is defined as an ordered pair $G = (V, E)$, where:

• $V = \{v_1, v_2, ..., v_n\}$ is the set of vertices (a finite or infinite collection of points)
• $E = \{(v_i, v_j) | v_i, v_j \in V\}$ is the set of edges (a collection of connections between vertices)

Key Terminology:

• If an edge connects two vertices $v_1$ and $v_2$, we denote the edge by $v_1v_2$ (which is the same as $v_2v_1$ in an undirected graph)
• Two vertices are said to be adjacent (or neighbors) if they are connected by an edge
• An edge is said to be incident to the vertices it connects

Visualizing Graphs: Many Ways to Draw the Same Structure

One of the beautiful aspects of graphs is that the visual layout doesn’t matter—only the connections do! The same graph can be drawn in countless different ways.

Important insight: Shown above are several ways of drawing the same graph. Notice that all three representations have the same structure—a string of five vertices connected in a row. The vertices might be positioned differently, but the connections remain identical.

This is a crucial concept: Two graphs are the same if they have the same vertices and the same connections, regardless of how they’re drawn. This property is called graph isomorphism.

Example: A Simple Social Network

One of the most intuitive examples of a graph is a social network. Let’s model a small group of friends and see how graph theory helps us understand their relationships.

The Scenario:

• Vertices ($V$): Each person is a vertex. Let’s take four friends: Alice, Bob, Charlie, and Diana.

  • So, $V = \{Alice, Bob, Charlie, Diana\}$
  • This gives us $|V| = 4$ vertices (the order of our graph)

• Edges ($E$): Each friendship is an edge connecting two people.

  • Alice is friends with Bob
  • Alice is also friends with Charlie
  • Bob and Charlie are friends
  • Charlie is friends with Diana

The set of edges is $E = \{\{Alice, Bob\}, \{Alice, Charlie\}, \{Bob, Charlie\}, \{Charlie, Diana\}\}$

This gives us $|E| = 4$ edges (the size of our graph).

Interactive Visualization:

Here is an interactive representation of this social network. You can drag the nodes around to explore how they are connected!

What Can We Learn?

This simple visualization reveals several interesting insights about the social structure:

1. Direct Connections: Alice and Diana are not directly connected—they aren’t friends with each other
2. Indirect Paths: However, Alice can reach Diana through Charlie (Alice → Charlie → Diana)
3. Central Figure: Charlie is connected to the most people (3 friends), making him the most central person in this network
4. Isolated Groups: If we removed Charlie, the network would split into two separate groups!

These observations demonstrate the power of graph theory—it helps us see patterns and structures that might not be immediately obvious from a list of friendships.

A Real-World Analogy: The Road Network

Let’s explore another example that makes graphs even more concrete: a road network.

Imagine a small region with towns and roads:

• Vertices: Towns (Springfield, Riverside, Hilltop, Lakeside)
• Edges: Roads connecting the towns

In this representation:
- Each town is a vertex
- Each road is an edge connecting two towns
- You can travel between any two towns that share an edge

This is exactly the kind of problem GPS systems solve every day—finding the best route between locations using graph algorithms!

Interactive Road Network:

Here’s our road network graph with 4 towns and 5 roads. Drag the towns around to explore the connections!

Analyzing the Network:

Let’s examine this road network using graph theory concepts:

• Order: $|V| = 4$ (four towns)
• Size: $|E| = 5$ (five roads)
• Degree of each vertex:
• Springfield: degree 2 (connected to Riverside and Hilltop)
• Riverside: degree 3 (connected to Springfield, Hilltop, and Lakeside)
• Hilltop: degree 3 (connected to Springfield, Riverside, and Lakeside)
• Lakeside: degree 2 (connected to Riverside and Hilltop)

Key Questions We Can Answer:

• Which towns are directly connected?
• Springfield ↔ Riverside, Springfield ↔ Hilltop
• Riverside ↔ Hilltop, Riverside ↔ Lakeside

• Hilltop ↔ Lakeside

• What’s the shortest path between two towns?

• Springfield to Lakeside: Two options!

  • Via Riverside: Springfield → Riverside → Lakeside (2 roads)
  • Via Hilltop: Springfield → Hilltop → Lakeside (2 roads)

• If one road closes, can we still reach all towns?

• Yes! This network has redundancy. If any single road closes, you can still reach all towns via alternative routes.

• Try it: If the Springfield-Riverside road closes, you can still go Springfield → Hilltop → Riverside

• Which town is most centrally located?

• Riverside and Hilltop both have degree 3, making them the most connected towns
• They serve as central hubs in this network!

Understanding Graph Notation

Before we go further, let’s understand how mathematicians write about graphs:

Set Notation:
- $V = \{A, B, C, D\}$ means “the set of vertices contains A, B, C, and D”
- $|V| = 4$ means “the number of vertices is 4” (called the order of the graph)
- $|E| = 3$ means “the number of edges is 3” (called the size of the graph)

Edge Notation:
- $\{A, B\}$ represents an undirected edge between vertices A and B
- $(A, B)$ represents a directed edge from A to B (we’ll learn about this later!)
- $v_1v_2$ is shorthand for the edge connecting $v_1$ and $v_2$

Adjacency:
- If $\{A, B\} \in E$, we say “A and B are adjacent” or “A is a neighbor of B”
- The set of all neighbors of vertex $v$ is called the neighborhood of $v$

Why Do Graphs Matter?

Graphs are more than just a mathematical curiosity; they are a fundamental tool for understanding and solving real-world problems. They provide a common language and a set of powerful algorithms that can be applied across countless domains.

Applications Across Fields

1. Computer Science & Technology
* Network Routing: How does data find the fastest path across the internet? Graph algorithms!
* Database Design: Organizing and querying connected data (think: social networks, recommendation systems)
* Compiler Optimization: Analyzing program structure and dependencies
* Artificial Intelligence: Knowledge graphs, decision trees, neural networks
* Web Search: PageRank algorithm (the foundation of Google) uses graph theory

2. Biology & Medicine
* Protein Interaction Networks: Understanding how proteins interact in cells
* Disease Spread Modeling: Tracking how diseases propagate through populations
* Brain Connectivity: Mapping neural pathways and understanding brain function
* Evolutionary Trees: Representing relationships between species

3. Social Sciences
* Social Network Analysis: Understanding influence, community structure, and information spread
* Epidemiology: Modeling disease transmission through contact networks
* Organizational Analysis: Studying collaboration patterns and communication flows
* Market Research: Analyzing consumer behavior and product relationships

4. Logistics & Transportation
* Route Optimization: Finding shortest paths, vehicle routing, delivery planning
* Traffic Flow Analysis: Understanding and managing congestion
* Supply Chain Management: Optimizing distribution networks
* Public Transit Planning: Designing efficient transportation systems

5. Telecommunications
* Network Design: Building efficient communication networks
* Load Balancing: Distributing traffic across network resources
* Fault Tolerance: Ensuring connectivity even when components fail
* Bandwidth Optimization: Maximizing data throughput

6. Operations Research & Engineering
* Scheduling Problems: Task dependencies and resource allocation
* Circuit Design: Analyzing electronic circuits and connections
* Project Management: PERT/CPM charts for project planning
* Resource Allocation: Optimizing the distribution of limited resources

Graphs Are Everywhere: Unexpected Examples

Once you understand graphs, you’ll start seeing them everywhere! Here are some surprising examples:

Your Morning Routine:
- Vertices: Tasks (shower, breakfast, get dressed, brush teeth)
- Edges: Dependencies (you must shower before getting dressed)
- This is a directed acyclic graph (DAG) representing task ordering!

A Chess Game:
- Vertices: Board positions
- Edges: Legal moves from one position to another
- This creates a massive graph of all possible chess games!

Airport Connections:
- Vertices: Airports worldwide
- Edges: Direct flights between airports
- Weights: Flight time, cost, or distance
- Your travel booking site uses graph algorithms to find the best routes!

Movie Recommendations:
- Vertices: Movies and users
- Edges: “User watched movie” or “Movies are similar”
- Netflix uses graph algorithms to recommend what you should watch next!

The Power of Graph Thinking

By understanding the basics of graphs, you unlock a new way to see and solve complex problems. Graph theory gives you:

1. A Visual Language: Complex relationships become easier to understand when drawn as graphs
2. Pattern Recognition: Structural patterns emerge that are hidden in raw data
3. Problem-Solving Tools: Centuries of mathematical research have produced powerful algorithms
4. Universal Applicability: The same concepts work across wildly different domains
5. Computational Power: Modern computers can analyze graphs with millions of vertices

The Journey Ahead:

In this blog series, we’ll explore:
- Different types of graphs (directed, weighted, bipartite, and more)
- Fundamental graph properties (degree, paths, cycles, connectivity)
- Classic graph algorithms (shortest paths, minimum spanning trees, graph coloring)
- How to apply graph theory to solve real problems

Whether you’re a student, programmer, data scientist, or just curious about mathematics, graph theory offers insights and tools that will change how you think about problems.

Ready to dive deeper? Let’s continue our journey by exploring the different types of graphs in the next post!

Quick Terminology Reference

Here’s a handy reference of terms we’ve learned:

Next Up: Common Types of Graphs →

Learn about directed graphs, weighted graphs, trees, and many other special types of graphs!