At its core, a graph is a way to represent connections. Think of your social network. You and your friends are the points, and the friendships between you are the lines connecting those points. In graph theory, we have special names for these things.

A graph is simply a collection of nodes and edges. We can describe a graph, $G$, as a pair of sets, $V$ for vertices (nodes) and $E$ for edges. This is often written as $G = (V, E)$. Let's see what a simple one looks like.

In the graph above, the nodes are {A, B, C, D, E}, and the edges represent the connections between them. But not all connections are the same. This leads to different types of graphs.

Edges can tell us more about the relationship between nodes depending on the type of graph.

Undirected Graphs In an undirected graph, edges represent a two-way relationship. If node A is connected to node B, then B is also connected to A. The graph we just saw is a perfect example. The edge is a simple line because the connection is mutual, like a friendship on Facebook.

Directed Graphs In a directed graph, or "digraph," the relationship is one-way. Think about X (formerly Twitter). You might follow someone, but that doesn't automatically mean they follow you back. These edges are drawn as arrows to show the direction of the connection.

Weighted Graphs Sometimes, the connection itself has a value. A weighted graph assigns a number, or "weight," to each edge. This could represent the distance between two cities on a map, the cost of a flight, or the strength of a connection. These graphs can be either directed or undirected.

By examining a graph's structure, we can uncover useful information. This involves looking at a few basic properties.

In an undirected graph, the degree of a node is simply the count of its connections. For directed graphs, it's more specific:

• In-degree: The number of edges pointing to a node.
• Out-degree: The number of edges pointing away from a node.

Next, we have paths and cycles.

A path is a sequence of nodes where each adjacent pair is connected by an edge. It's like finding a route from a starting point to a destination.

A cycle is a path that starts and ends at the same node, forming a loop. You can leave a node and, by following a path, find your way back to it without retracing your steps.

These building blocks—nodes, edges, and their properties—are the foundation of graph theory. They give us a powerful language to describe and analyze networks of all kinds.

Ready to check your understanding? Let's try a few questions.