MATH FOR COMPUTER SCIENCE · BEGINNER NOTES

Graph theory, without the intimidation.

You do not need advanced calculus to start graph theory. Begin with dots, lines, and questions about how things are connected.

Dark cyan and violet network artwork representing vertices and edges
FIG. 01 / A NETWORK — Each glowing point is a vertex; each line is an edge.
The whole idea in one sentence: a graph is a collection of vertices (dots) and edges (connections between dots).

1. Why do computer scientists care?

Think of a social network. Each person is a vertex; a friendship is an edge. Or think of the internet: pages are vertices and links are edges. Roads between cities, computers on a network, and dependencies between software packages can all be described with graphs.

Graph theory gives us a compact language for asking questions such as: Can I get from A to B? Which person has the most direct connections? Are there separate groups? What happens if a connection breaks?

ABCDEFG
FIG. 02 / VERTICES & EDGES — The same graph can be drawn in many layouts; its connections are what matter.

2. Six words worth knowing

Vertex (plural: vertices)

One item in your network. We often label vertices 1, 2, 3, and so on.

Edge

A connection between two vertices. In a simple undirected graph, an edge from A to B is the same as an edge from B to A.

Degree

The number of edges touching a vertex. If vertex 2 connects to vertices 1, 3, and 4, its degree is 3.

Path

A sequence of edges that lets you travel from one vertex to another.

Connected graph

A graph is connected if every vertex can reach every other vertex along some path.

Cycle

A path that returns to where it started without repeating the intermediate vertices.

12345Σ degree(v)= 2 |E|each edge hastwo endpoints
FIG. 03 / THE HANDSHAKE LEMMA — Add every vertex degree and each edge is counted twice.

3. A small counting trick

In an undirected graph, every edge touches two endpoints. So when we add up all vertex degrees, each edge gets counted twice.

sum of all degrees = 2 × number of edges

For example, if a graph has 5 edges, the sum of all degrees must be 10. This is called the handshake lemma: every edge represents a handshake between two endpoints.

DENSITYexisting ÷ possible edges0 = sparse · 1 = complete
FIG. 04 / DENSITY — Density compares existing edges with all edges that could exist.

4. What does “density” mean?

With n vertices, a simple undirected graph can have at most n(n−1)/2 edges—one for every possible pair of distinct vertices. Density tells us what fraction of those possible edges actually exist.

density = actual edges ÷ possible edges

A density near 0 means a sparse network. A density near 1 means almost every pair is connected. This helps compare networks of different sizes.

5. Try the interactive 3D playground

Open Graph Universe and test these small challenges. The graph rotates in 3D, but the mathematics is still the same: vertices and edges.

  1. Choose One popular hub. Which vertex has the largest degree?
  2. Choose A ring. Can you find two different paths between a pair of vertices?
  3. Add a dot. How do the vertex count and average degree change?
  4. Connect two dots. How many edges are there now?
  5. Drag a dot and rotate the scene. Notice that moving a vertex on screen does not change which vertices are connected.

Important distinction: moving a dot changes the drawing; adding or removing an edge changes the graph itself. A graph is about the connections, not the exact positions of the dots.

6. What to learn next

Once vertices, edges, degree, and paths feel familiar, explore breadth-first search (BFS), shortest paths, trees, bipartite graphs, and adjacency lists. These topics connect graph theory directly to algorithms and data structures in computer science.

OPEN GRAPH UNIVERSE — ROTATE, MOVE, AND BUILD YOUR OWN NETWORK ↗

Written as an introductory learning note. The playground is an educational model, not a full mathematical graph editor.