What is a graph? Vertices, edges, and basic notation
A graph is one of the most versatile structures in mathematics and computer science. At its core, a graph is simply a collection of vertices (also called nodes) connected by edges (also called links). This simple idea can model an incredible variety of real-world systems!
In this module, you'll build graphs from scratch, learn the essential terminology, and discover how graphs can be represented mathematically. Let's dive in!
Build your own graph! Click on the canvas to add vertices, then drag from one vertex to another to create an edge. This is the foundation of graph theory - vertices connected by edges.
A graph is written as G = (V, E) where V is the set of vertices and E is the set of edges. Your current graph has 0 vertices and 0 edges.
Hover over vertices and edges to learn the key terminology. The highlighted elements show relationships like neighbors and incident edges.
Complete graph with 3 vertices
Move your mouse over vertices and edges to see their properties and terminology.
Graphs can be undirected (edges have no direction) or directed (edges point from one vertex to another). Click a vertex, then click another to add an edge.
Edges: 4 | Edge notation: {u, v}
Edges: 4 | Edge notation: (u, v) or u ā v
Degree = total number of edges connected
In-degree = edges coming in, Out-degree = edges going out
Undirected
Directed
An adjacency matrix represents a graph as a 2D array. Click cells to toggle edges and watch the graph update in real-time!
Click a cell to toggle the edge. Diagonal is always 0 (no self-loops).
Adjacency matrices are ideal for dense graphs (many edges) and algorithms that need fast edge lookups. For sparse graphs (few edges), adjacency lists are more space-efficient. The matrix also enables powerful linear algebra techniques - matrix powers reveal path counts between vertices!
1. Graph Basics: A graph G = (V, E) consists of vertices V and edges E. Edges connect pairs of vertices to represent relationships.
2. Terminology: The degree of a vertex is the number of edges connected to it. Neighbors are vertices connected by an edge. Adjacent vertices share an edge.
3. Directed vs Undirected: In undirected graphs, edges have no direction (friendships). In directed graphs (digraphs), edges point from source to target (followers, web links).
4. Adjacency Matrix: A VĆV matrix where A[i][j] = 1 if there's an edge from vertex i to j. Symmetric for undirected graphs. Great for dense graphs and fast edge lookup.
Next Up: In the next section, you'll learn about graph properties like connectivity, special graph types (complete, bipartite, trees), and the famous Handshaking Lemma!