Graphs sound intimidating because of words like "articulation point" and "strongly connected" — but at the core, a graph is just dots connected by lines. That's it. Everything else is just describing how those dots and lines behave.

The dots are called vertices (one dot = a "vertex"), and the lines are called edges. So really, a graph is just "some vertices, and some edges connecting them."

Four circles labeled 1, 2, 3, 4 scattered on a page with a couple of plain lines connecting some of them, with labels pointing to a vertex and an edge

Once you're comfortable with that picture — dots and lines — here's the fancy math way people write it, just so it doesn't surprise you later:

G = (V, E)

This just means: a graph G is made of two things — a set of vertices V (all the dots) and a set of edges E (all the lines). Nothing new, just notation for the same picture you already have in your head.

Directed vs Undirected: Do the Lines Have Arrows?

This is the very first fork in the road, and it decides everything else.

Directed Graph (arrows point somewhere)

If the lines have arrows, it's a Directed Graph. An arrow from 1 → 2 means you can go from 1 to 2, but that does NOT automatically mean you can go from 2 back to 1.

1 → 2

Think of it like a one-way street. You can drive from 1 to 2, but you can't just turn around and drive back unless there's a separate arrow pointing the other way.

Four circles labeled 1, 2, 3, 4 arranged in a square with arrows forming a directed cycle: 1→2, 2→3, 3→4, 4→1, titled Directed Graph

Undirected Graph (no arrows, just lines)

If the lines are plain, with no arrows, it's just called a Graph (or "undirected graph"). A line between 1 and 2 means you can move freely both ways — 1 to 2 AND 2 to 1.

1 — 2

Think of it like a regular two-way street.

Four circles labeled 1, 2, 3, 4 arranged in a square connected by plain lines with no arrowheads, titled Undirected Graph
Quick rule
Arrows = directed. No arrows = undirected. That's the whole distinction.

Self Loop

A self loop is exactly what it sounds like — an edge that starts and ends at the same vertex. It's a dot pointing back at itself, like a little loop-the-loop.

A single circle labeled 1 with a small curved loop coming out of the top and re-entering the same circle with an arrowhead, labeled Self Loop

Nothing connects to anything new here — the vertex is just connected to itself.

Parallel Edges

Parallel edges are when there are two or more edges between the exact same pair of vertices.

Example: if there's an edge 4 → 3 AND another edge 3 → 4, both connecting the same two dots (just going opposite directions, or even the same direction twice), that's a parallel edge situation.

Two circles labeled 3 and 4 connected by two separate curved arrows — one curving above going from 4 to 3, one curving below going from 3 to 4, labeled Parallel Edges

Why does this matter? Because it changes what "type" of graph you have:

  • A graph with self loops and/or parallel edges → just called a Directed Graph (the general, "anything goes" version)
  • A graph without self loops and without parallel edges → called a Simple Digraph (the "clean" version)

So "simple" here doesn't mean "easy" — it means "no self loops, no parallel edges." Good to know, because it trips people up.

A clean directed graph labeled Simple Digraph with 4 circles labeled 1, 2, 3, 4, with arrows 1→2, 1→4, 1→3, 4→3, 3→2, no loops or parallel edges

Degree, Indegree, and Outdegree — Counting the Lines

This is just counting how many edges touch a vertex. But it's counted differently depending on directed vs undirected.

For Undirected Graphs → just "Degree"

Degree = how many edges are touching that vertex, full stop.

Example: if vertex 1 has 3 lines coming out of it (to vertices 2, 3, and 4), then:

degree of vertex 1 = 3
Vertex 1 at the top connected by three plain lines down to three circles labeled 2, 3, 4 spread below it, labeled degree 3

For Directed Graphs → "Indegree" and "Outdegree" (two separate counts)

Since directed edges have a direction, we split the counting into two:

  • Indegree = how many arrows are pointing INTO the vertex
  • Outdegree = how many arrows are pointing OUT OF the vertex

Example: vertex 4 has two arrows coming in (from vertex 1 and vertex 3) and one arrow going out (to vertex 3):

Indegree of 4  = 2
Outdegree of 4 = 1
Vertex 4 in the middle with two arrows pointing into it from vertices 1 and 3, and one arrow pointing out toward vertex 3, labeled Indegree 2 and Outdegree 1
Easy way to remember
"In" = arrows walking IN. "Out" = arrows walking OUT. The words are literally telling you what to count.

Path — Just a Route You Can Walk

A path is simply a sequence of vertices you can travel through, one edge at a time, following the arrows (if directed).

Example: 1 → 2 → 5 is a path — you start at 1, walk the edge to 2, then walk the edge to 5.

A directed graph with circles labeled 1, 2, 3, 4, 5 with arrows 1→2, 2→5, 3→4, 4→2, with the path 1→2→5 highlighted in red, labeled Path

Nothing fancier than "can I trace a route from here to there using existing edges?"

Connected vs Non-Connected — Can Everyone Reach Everyone?

Non-Connected Graph

If the graph is split into separate "islands" — groups of vertices where you can't get from one island to another — it's called non-connected, and each island is called a component.

Example: if vertices {1,2,3,4} are all linked to each other, but {5,6,7} are linked only to each other and NOT to the first group, then this graph has 2 components.

An undirected graph split into two separate clusters — left cluster has circles 1, 2, 3, 4 connected together, right cluster has circles 5, 6, 7 connected together, with a visible gap between them, labeled 2 components in red

Articulation Point

An articulation point is a vertex that, if you removed it, would split the graph into more pieces — breaking the connection between other vertices.

Think of it like a bridge vertex — it's the one thing holding two parts of the graph together. Remove it, and the graph falls apart into more components.

An undirected graph shaped like two clusters connected only through a single middle circle labeled 4 — left side has circles 1, 2, 3 connected to vertex 4, right side has circles 5, 6, 7 connected to vertex 4, with vertex 4 highlighted in red and labeled Articulation Point

Strongly Connected (Directed Graphs Only)

A directed graph is strongly connected if, for every pair of vertices, you can get from one to the other AND back — following the arrows both ways.

So it's not enough to reach a vertex — you also need to be able to return. If every vertex can reach every other vertex (round trip, respecting arrow direction), the whole graph is strongly connected.

A small directed graph with circles labeled 1, 2, 3, 4, 5 with arrows forming a full directed cycle so every vertex can reach every other and return, titled Strongly Connected

Directed Acyclic Graph (DAG)

A DAG is a directed graph with one special rule: no cycles allowed.

A "cycle" means a loop where you start at a vertex, follow arrows around, and end up back where you started. A DAG guarantees that can never happen — once you leave a vertex, there's no path of arrows that leads you back to it.

1 → 2 → 5
3 → 4 → 6
2 → 5 (no way back from 5 to 1, 2, 3, or 4)
A directed graph with 6 circles labeled 1, 2, 3, 4, 5, 6 in two rows with arrows 1→2, 2→5, 1→3, 3→4, 4→6, 4→5, all flowing left to right with none pointing backward, titled Directed Acyclic Graph (DAG)

DAGs show up everywhere — task scheduling, prerequisite chains (like course prerequisites), build systems — anywhere "this must happen before that" and nothing is allowed to loop back on itself.

Topological Ordering

Topological ordering is just a way of lining up all the vertices of a DAG in a single row, such that every arrow points forward (left to right), never backward.

Example ordering: 1 → 3 → 2 → 4 → 5 → 6

Six circles labeled 1, 3, 2, 4, 5, 6 arranged in a single horizontal row with arrows all pointing rightward or in gentle forward arcs, titled Topological Ordering

This is basically a valid "order to do things in" — if vertex 1 must happen before vertex 3, and 3 before 2, this ordering respects all of that.

Key insight
Only DAGs have topological orderings. If there's a cycle, you can never arrange everything left-to-right without an arrow pointing backward somewhere — that's actually one way to prove a graph is NOT a DAG.

Where You'll Actually See This In Real Life

All of this isn't just whiteboard theory — here's where each concept shows up in things you already use:

Concept Real-life example
Undirected Graph Facebook/Instagram friendships — if you're friends with someone, they're friends with you too. Two-way, no arrows needed.
Directed Graph Instagram following (not friends) — you can follow someone without them following you back. One-way arrow.
Self Loop A flight that departs and lands at the same airport, or a function in code that calls itself.
Parallel Edges Multiple direct flights between the same two cities on different airlines — same two vertices (cities), multiple edges (flights).
Degree / Indegree / Outdegree On Twitter/X, your outdegree is how many people you follow, your indegree is how many followers you have.
Path Google Maps giving you turn-by-turn directions — literally a path traced through a graph of roads (vertices = intersections, edges = roads).
Connected Components A messaging app's "friend groups" — if group A has never interacted with group B at all, they're separate components.
Articulation Point A single server or router that, if it goes down, splits part of the internet off from the rest — a literal single point of failure.
Strongly Connected A subway system where every station can reach every other station, and you can always get back — round trips work everywhere.
DAG Course prerequisites in college — you can't have "Course A requires Course B" and "Course B requires Course A" at the same time, or nobody could ever start.
Topological Ordering A recipe's step order, or a build system like make/CI pipelines — figuring out a valid sequence to do things in so nothing runs before its prerequisite.

Quick Reference Table

Term Meaning
Vertex a dot / node
Edge a line connecting two dots
Directed Graph edges have arrows (one-way)
Undirected Graph edges have no arrows (two-way)
Self Loop an edge from a vertex to itself
Parallel Edges 2+ edges between the same pair of vertices
Simple Digraph directed graph with NO self loops or parallel edges
Degree (undirected) total edges touching a vertex
Indegree (directed) arrows coming IN
Outdegree (directed) arrows going OUT
Path a route from vertex to vertex along edges
Component a connected "island" of vertices
Articulation Point a vertex that, if removed, splits the graph further
Strongly Connected every vertex can reach every other vertex, both ways
DAG directed graph with no cycles
Topological Ordering lining up vertices so every arrow points forward

Quick Quiz

  1. If an edge has an arrow, is the graph directed or undirected?
  2. What do you call an edge that loops back to the same vertex it started from?
  3. In a directed graph, does "indegree" count arrows coming in, or going out?
  4. What's the key rule that makes a directed graph a DAG?
  5. If removing a vertex splits the graph into more pieces, what is that vertex called?
Answers
  1. Directed.
  2. A self loop.
  3. Coming in.
  4. No cycles — you can never follow arrows back to where you started.
  5. An articulation point.

One-Line Summary

A graph is just dots and lines. Arrows or no arrows decides directed vs undirected. Degree/indegree/outdegree just count edges touching a vertex. Components tell you if everyone's connected. A DAG is a directed graph that never loops back on itself, and topological ordering lines it all up left to right.