Graph Anatomy

The vocabulary page. Every other graph page on this site - and every problem statement you will ever read - assumes you already know what a vertex, an edge, a degree, and a path are, assumes you will not mix up the four words that all sort of mean "a walk through the graph," and assumes you know exactly where the tree you already know fits inside this bigger picture. This page is that foundation, drawn out. Representation picks up from here with how a graph is stored; this page is only about what one is.

1. Vertices and edges

A graph is two sets and nothing else: a set of vertices and a set of edges joining pairs of them. That is the whole definition. Everything else on this page is a name for some pattern those two sets can form.

• A vertex (plural vertices; also called a node) is one thing. A city, a person, a web page, a course, a grid cell, a program state.
• An edge (also called a link or an arc when directed) is one relationship between two vertices. The two vertices an edge joins are its endpoints.

The formal notation, which problem statements and papers use without explanation: a graph is written $G = (V, E)$, where $V$ is the vertex set and $E$ the edge set. $|V|$ (usually written just n or V in code) is the order of the graph; $|E|$ (m or E) is its size. An undirected edge is an unordered pair $\{u, v\}$ - so $\{u,v\}$ and $\{v,u\}$ are the same edge - while a directed edge is an ordered pair $(u, v)$, and $(u,v)$ and $(v,u)$ are two different edges.

Four words get used constantly and mean four slightly different things.

Adjacent, Endpoint and Incident all describe the same edge {u,v}; Neighbour needs the second edge {v,w} too.

Word	Relates
	Reading of the diagram above
Adjacent	vertex to vertex
	u and v are adjacent. u and w are not - no single edge joins them.
Neighbour	vertex to vertex
	The neighbours of v are {u, w}. Same relation as adjacency, said from one vertex's point of view.
Incident	vertex to edge
	v and w are incident to edge {v,w} - the vertex is the subject. A vertex is never "incident" to another vertex.
Endpoint	edge to vertex
	The endpoints of edge {u,v} are u and v. The same relation read from the edge's side.

⚠

Size means edge count, not vertices

"Size" of a graph means its edge count, not its vertex count. Complexity bounds trade on this: $O(V + E)$ is linear in the size of the graph, and that is two numbers, not one. When a problem says "the graph is large," ask which of the two is large - a million vertices with a thousand edges and a thousand vertices with a million edges want different code.

2. Degree

The degree of a vertex is how many edge-ends touch it. In an undirected graph that is just "how many neighbours it has," with one exception covered below. Degree is the cheapest non-trivial fact about a graph: you can compute every vertex's degree in one pass over the edge list, without building an adjacency list and without traversing anything.

Names for the degrees that come up in problem statements:

• Isolated vertex - degree 0. No edges at all. These are the vertices that silently vanish when you build an adjacency list from an edge list only, which is its own trap on the Representation page.
• Pendant vertex (or leaf) - degree 1. Hanging off the graph by a single edge.
• Self-loop - an edge from a vertex to itself. It contributes 2 to that vertex's degree, because both of its ends land on the same vertex.

⚠

Self-loop adds 2 to degree, not 1

A self-loop adds 2 to the degree, not 1. It is the one case where "degree" and "number of distinct neighbours" disagree. Most interview problems forbid self-loops outright, so this rarely bites in practice - but it is the standard gotcha in any written graph-theory question, and it is what keeps the handshake lemma below exactly true.

The handshake lemma

Sum every vertex's degree and you always get exactly twice the edge count:

$\sum_{v \in V} \deg(v) = 2|E|$

Every edge has two ends, and each end lands on exactly one vertex, so each edge is counted exactly twice by the sum. That is the whole proof.

Two things this buys you cheaply:

• A quick sanity check on your own code. If your degree array does not sum to 2 * len(edges), you have either double-counted an undirected edge or dropped one direction of it.
• The average degree. It is $2|E|/|V|$, not $|E|/|V|$ - which is what makes "average degree 4" mean roughly 2E = 4V, i.e. a sparse graph. It is also why an adjacency list's per-vertex cost is "degree," a number that averages to a small constant on real graphs, rather than $|V|$.

In-degree and out-degree

Once edges have a direction, one number is not enough - an edge pointing at a vertex is a different fact from one pointing away from it.

• in-degree of v = how many edges end at v (how many point in)
• out-degree of v = how many edges start at v (how many point out)

Signal	Means
	Where it shows up
in-degree 0	nothing depends on it / nothing points at it - a source
	Kahn's algorithm starts from exactly these (Cycles & Ordering)
out-degree 0	it points at nothing - a sink, terminal, or final state
	"which city is the end of the trip", eventual-safe-states
in-degree n - 1	every other vertex points at it
	town judge, celebrity, champion
out-degree 0 and in-degree n - 1	the unique thing everyone knows that knows nobody
	the exact spec of LC 277 Find the Celebrity

The directed twin of the handshake lemma is even simpler, and just as useful as a self-check:

$\sum_{v \in V} \deg^{-}(v) = \sum_{v \in V} \deg^{+}(v) = |E|$

⚠

Degree questions rarely need traversal

Degree questions rarely need a traversal at all. A whole family of problems - town judge, destination city, find the champion, minimum vertices to reach all nodes - is solved by one pass building an in-degree/out-degree count and one pass reading it off. Reaching for BFS is not wrong, it is just an adjacency list and a queue you never needed. The Degree practice set is exactly this reflex.

3. Walks, trails, paths, and cycles

These four are the words most often used interchangeably and wrongly. All four describe a sequence of vertices where each consecutive pair is joined by an edge. They differ only in what you are allowed to repeat.

Name	May repeat vertices?	May repeat edges?	Closed version
Walk	yes	yes	closed walk
Trail	yes	no	circuit
Path	no	no (follows from the above)	cycle

"Closed" just means it ends where it started. So a cycle is a path that returns to its start, and a circuit is a trail that returns to its start.

Edges: A-B, B-C, B-D, A-D, D-C, C-E.

Sequence	What it is
	Why
A B A B C	a walk, nothing more
	The edge A-B is crossed twice, which disqualifies it from being a trail.
A B D C B	a trail, not a path
	No edge repeats, but the vertex B appears twice.
A B C E	a path (a simple path)
	No vertex repeats. Length 3 - three edges, four vertices. This is what "path" means in every problem statement.
A B D A	a cycle of length 3
	Closed, three distinct vertices, no repeated edge. The smallest cycle an undirected graph can have.
A B C D A	a cycle of length 4
	Also closed and edge-disjoint. A graph can hold many cycles at once; this one and the previous share the edge A-B.

⚠

"Path" means simple path by default

When a problem says "path," it almost always means simple path - no repeated vertices. "Find if a path exists," "shortest path," "count paths in a DAG" all mean the simple kind. If repeats were allowed, "shortest path" in a graph with a zero-weight cycle would have infinitely many answers, and "count paths" would be infinite the moment a cycle existed anywhere. The word "simple" is usually left implicit; assume it, and reread the constraints if the answer comes out infinite.

Two more length-related facts worth having:

• The length of a path is its edge count, not its vertex count. A B C E has length 3 and visits 4 vertices. Off-by-ones in BFS distance code are almost always this: BFS returns the number of edges crossed, so a problem asking for "the number of nodes on the shortest path" wants distance + 1.
• A cycle needs at least 3 distinct vertices in an undirected graph, but only 2 in a directed one. Walking A-B then back B-A on a single undirected edge reuses that edge, so it is not a cycle - it is a closed walk. In a directed graph A→B and B→A are two genuinely different edges, so that is a cycle of length 2. This single asymmetry is why undirected and directed cycle detection are written differently; see Cycles & Ordering.

4. Simple graphs, multigraphs, and loops

The default graph in every interview problem is a simple graph: no self-loops, and at most one edge between any pair of vertices. The two ways to break that have names, and both change what your code has to handle.

Kind	Definition
	What breaks in code
Simple graph	No self-loops, no parallel edges. The default assumption.
	Nothing. Every idiom on this site assumes it.
Multigraph	Two or more parallel edges joining the same pair.
	A boolean adjacency matrix cannot store the multiplicity (you would need a count). An adjacency list stores the duplicate fine, but a visited set makes the second copy invisible to traversal - which is correct for reachability and wrong for anything counting edges.
Loop / pseudograph	An edge from a vertex to itself.
	It sits on the adjacency matrix diagonal M[i][i], which is why matrix-neighbour code carries an and j != i guard. In a visited-guarded DFS it is a harmless no-op.
Complete graph K_n	Every pair of distinct vertices joined by exactly one edge.
	Nothing breaks, but |E| = n(n-1)/2 (every pair, once), so an adjacency matrix is finally the right choice - it is the one shape where O(V^2) space is not waste.

⚠

Duplicate edges aren't the same as multigraphs

A duplicate edge in the input is not the same as a multigraph in your model. Problem inputs regularly hand you [[0,1],[1,0]] for a single undirected edge, or repeat an edge outright. Building an adjacency list naively then gives adj[0] == [1, 1], and any code that counts edges by summing len(adj[u]) is now wrong by a factor of two. Traversal survives it (the visited set absorbs the duplicate); anything counting does not.

5. Dense, sparse, and how many edges are even possible

An undirected simple graph on n vertices has at most $\binom{n}{2} = n(n-1)/2$ edges (every pair, once), and a directed one at most $n(n-1)$ (every ordered pair). Where a graph sits between 0 and that ceiling is the whole basis of "which representation should I use."

Term	Roughly means
	Consequence
Sparse	|E| is close to |V| - average degree is a small constant
	Adjacency list. O(V+E) is essentially O(V). This is nearly every real graph and nearly every interview graph.
Dense	|E| is close to |V|^2
	Adjacency matrix earns its space. O(V+E) is really O(V^2), so a V^2 matrix costs nothing extra.
Complete (K_n)	the maximum: every pair joined
	The dense extreme. n = 1000 already means half a million edges.

⚠

Sparse/dense is about ratio, not count

"Sparse" and "dense" are about the ratio, not the absolute count. A graph with a million edges is sparse if it has a million vertices and dense if it has two thousand. When a complexity bound is quoted as $O(V + E)$ or $O(E \log V)$, the only way to know whether that is fast is to know which regime you are in.

6. Weighted graphs

An edge can carry a number - a weight - meaning distance, cost, capacity, time, or probability. Nothing about the vocabulary above changes; the weight just rides along on the edge.

⚠

Weight belongs to the edge, not the vertex

A weight is a property of an edge, not of a vertex. Problems that put a cost on entering a vertex (a toll per city, a time per task) are not weighted-edge problems as stated - you either push the vertex cost onto every edge that enters it, or split each vertex into an in-copy and an out-copy joined by one edge carrying the cost. Trying to shoehorn vertex weights into Dijkstra's edge relaxation directly is a common source of off-by-one-vertex totals.

7. Connectivity vocabulary

• A graph is connected when every vertex can reach every other vertex by some path. If it cannot, it splits into connected components - maximal groups of mutually reachable vertices. A single vertex with no edges is a component all by itself.
• Direction complicates this, so directed graphs get two words: weakly connected means connected if you ignore all the arrow directions, and strongly connected means every vertex can reach every other while respecting the directions. The maximal strongly-connected groups are strongly connected components (SCCs), covered in MST & SCC.
• A DAG is a directed acyclic graph - directed, with no directed cycle. Every dependency-ordering problem lives here, because a valid order exists exactly when the graph is a DAG.

Weakly connected as a whole (ignore the arrows), despite two separate strongly connected components (obey them).

8. Why a graph is not just a bigger tree

A graph is a non-linear structure: unlike an array or a linked list, there is no single order to walk through every element in. From a given vertex there can be zero, one, or many ways to reach another, and which ones exist is exactly what the edge set encodes. A tree is the special case where that freedom is cut back to "exactly one way between any two vertices" - which is why almost every tree habit needs one adjustment before it survives on a graph.

⚠

Degree is not child count; connected is not tree

Degree ≠ child count, and connected ≠ tree. A node's degree is how many edges touch it - in an undirected graph a node in the middle of a path has degree 2 even though it's nobody's "child" the way a tree node is. And a tree is connected and acyclic - equivalently, connected with exactly N-1 edges; one extra edge guarantees a cycle. len(edges) == n - 1 is an O(1) tree check.

The one non-negotiable habit once you start writing traversal code: mark before you walk. A visited set is the seatbelt that stops a cycle from looping you forever. Trees don't need one (no cycles, exactly one path between any two nodes); general graphs always do - the four properties on the next page are what decide just how much a graph can loop back on itself.

9. Graph vs tree vs forest

Trees and forests are graphs - just graphs with extra promises attached. Precisely, using $G = (V, E)$ for a graph with vertex set $V$ and edge set $E$:

• Graph: $G = (V, E)$ where $E \subseteq \{\{u, v\} : u, v \in V\}$ (undirected) or $E \subseteq V \times V$ (directed). No other constraint - cycles, disconnection, multiple components are all allowed.
• Tree: a graph that is both connected (every vertex reachable from every other) and acyclic (no cycles). Equivalently - and this equivalence is worth memorising, it's where the |E| == |V| - 1 check comes from - a tree is any of these, and having one guarantees all the others:
  • connected and acyclic
  • connected with exactly $|V| - 1$ edges
  • acyclic with exactly $|V| - 1$ edges
  • exactly one simple path between every pair of vertices
• Forest: an acyclic graph that is not required to be connected - a disjoint union of zero or more trees. A forest with $k$ connected components (i.e. $k$ separate trees) and $n$ vertices total has exactly $n - k$ edges; a tree is just the special case $k = 1$.

Forest : trees :: graph : connected components.

A forest is what you get by taking a graph, ripping out enough edges to kill every cycle, and not worrying about whether the pieces are still attached to each other. A tree is the same idea with one more promise: there's only one piece.

⚠

"Connected" isn't the same claim as "tree"

"Connected" is not the same claim as "tree." The left-hand graph above is connected - every vertex can reach every other - but the extra A-C edge closes a cycle through A-B-C, so it isn't a tree. Connectivity alone lets a cycle sneak in; a tree needs connectivity and the exact edge count that acyclicity forces.

10. The shape zoo

Five shapes come up by name often enough that recognising them on sight is worth more than any single algorithm. Each one is just a constraint on the edge set.

Shape	Recognise it by
	Why it matters
Path P_n	all degrees are 1 or 2, connected, acyclic
	The degenerate case that breaks tree code assuming branching, and the worst case for recursive DFS depth.
Cycle C_n	every degree is exactly 2
	|E| = |V|, the smallest possible non-tree. Odd n makes it non-bipartite; even n keeps it bipartite.
Star	one vertex of degree n-1, all others degree 1
	The worst case for "iterate my neighbours" - one vertex owns every edge. LC 1791 Find Center of Star Graph is literally "which vertex has degree n-1".
Complete K_n	every pair joined; all degrees n-1
	The dense extreme, and the case where an adjacency matrix is right.
Bipartite	vertices split into two sides, every edge crossing
	Equivalent to "contains no odd-length cycle" - see the 2-coloring check.

11. Subgraphs: taking a piece of a graph

Many algorithms are really "find the sub-piece of this graph with some property" - an MST is a spanning subgraph, a component is an induced subgraph, a matching is a subgraph where no two edges share a vertex. Three words distinguish which kind of piece you are allowed to take.

Kind	You may drop
	Canonical example
Subgraph	any vertices and any edges (dropping a vertex forces out every edge touching it)
	Any partial structure you build up edge by edge.
Induced subgraph on a vertex set S	only vertices - every original edge with both endpoints inside S must be kept
	A connected component. A clique. "Is this group mutually acquainted?"
Spanning subgraph	only edges - every vertex is kept
	A spanning tree, and therefore an MST (MST & SCC).

⚠

"Induced" removes freedom, doesn't add it

"Induced" is the word that removes your freedom, not the one that adds it. It is easy to read "induced subgraph" as "some subgraph I induced," i.e. any piece. It means the opposite: once you have chosen the vertices, the edge set is completely determined. A problem asking "does a group of k people all know each other" is asking about the induced subgraph on those k vertices being complete - you are not allowed to quietly ignore an inconvenient edge.

12. Isomorphism: the same graph, drawn differently

A picture of a graph is not the graph. Move the vertices around on the page, rename them, and you have the same graph - same vertices in the same relationships - wearing an unrecognisable drawing. Nothing about the graph itself says where a vertex sits on the page or how straight an edge is drawn

• a drawing is just one representation of the vertex set and edge set, and you can redraw the exact same graph by moving vertices around and changing how the edges curve:

Same graph (K4: 4 vertices, every pair adjacent) drawn three different ways.

Two graphs are isomorphic when you can relabel one into the other: there is a one-to-one mapping of vertices such that u and v are adjacent in the first exactly when their images are adjacent in the second.

Two drawings, one graph - the relabelling 1-2-3-4 to a-c-b-d maps one onto the other exactly.

Checking isomorphism in general is famously hard (no known polynomial algorithm, and it is not known to be NP-complete either - it sits in an awkward middle). But disproving it is usually easy, because isomorphic graphs must agree on every structural fact. Any mismatch below is an instant "no":

Invariant	Must match because
vertex count and edge count	relabelling cannot create or destroy either
degree sequence (all degrees, sorted)	a relabelled vertex keeps its degree
number of connected components, and their sizes	reachability is preserved by relabelling
girth (length of the shortest cycle)	a cycle maps to a cycle of the same length
number of triangles	same reason, for length-3 cycles specifically

⚠

Matching degree sequences don't prove isomorphism

A matching degree sequence does not prove isomorphism. It is necessary, never sufficient. The standard counterexample is two 6-vertex graphs where every vertex has degree 2: one is a single 6-cycle, the other is two disjoint triangles. Identical degree sequences, obviously different graphs - the component count gives it away. Any single invariant can be fooled; only a mismatch is conclusive.

A graph is planar when it can be drawn with no two edges crossing. The crossed drawing above is of a planar graph - the square drawing proves it - which is the whole point: crossings are a property of the drawing, planarity is a property of the graph.

For any connected planar drawing, Euler's formula relates vertices, edges and faces (the regions the drawing cuts the plane into, counting the infinite outer region):

$|V| - |E| + |F| = 2$

Two bounds fall straight out of it, and they are the fast way to prove something cannot be drawn flat: a simple planar graph with $|V| \ge 3$ has at most $3|V| - 6$ edges, and a bipartite one at most $2|V| - 4$. $K_5$ has 10 edges against a ceiling of 9, and $K_{3,3}$ has 9 against a ceiling of 8 - so neither is planar, and by Kuratowski's theorem those two are the only obstructions: a graph is planar exactly when it contains no subdivision of $K_5$ or $K_{3,3}$.

13. Edge taxonomy: every name an edge can have

"Edge" picks up a lot of adjectives, and they come from three completely different places. Confusing which place a name comes from is the source of most of the muddle:

1. Structural - a property of the graph itself. A bridge is a bridge no matter what you do to it.
2. Traversal-relative - a property of one particular DFS run. The same edge can be a tree edge in one DFS and a back edge in another, depending where you started.
3. Role in an answer - a property of a solution, not of the graph. An MST edge is only an MST edge relative to a chosen MST.

Structural edge types

Name	Definition
	Why it matters
Undirected edge	an unordered pair {u, v} - crossable both ways
	You append it to two adjacency lists. Forgetting the second append is the single most common graph-building bug.
Directed edge (arc)	an ordered pair (u, v) - one way only
	u -> v says nothing about v -> u. Two opposite arcs are a real 2-cycle.
Weighted edge	carries a number: cost, distance, capacity, time
	Turns "fewest hops" into "cheapest route" - see section 6.
Self-loop	both endpoints are the same vertex
	Adds 2 to that vertex's degree. Lives on the adjacency-matrix diagonal M[i][i], which is why matrix-neighbour code carries an and j != i guard.
Parallel edges (multi-edge)	two or more edges joining the same pair
	Makes the graph a multigraph. A boolean matrix cannot represent them; a visited set makes the duplicates invisible to traversal, which is right for reachability and wrong for counting.
Pendant edge	incident to a vertex of degree 1
	Always a bridge. Trees are made almost entirely of these at the fringe.
Bridge / cut edge	removing it increases the component count; equivalently it lies on no cycle
	The single-point-of-failure edge. Found with low-link in O(V + E) - see Bridges & articulation points.
Cycle edge / non-bridge	lies on at least one cycle
	It has an alternative route, so deleting it keeps the graph connected. Every edge in a 2-edge-connected component is one.
Incident edge	an edge touching a given vertex
	Not an edge type - a relation. See section 1.

Traversal-relative edge types

Run a DFS and it splits the edge set into exactly four classes, all relative to the DFS tree that the recursion builds. Two vertices' disc (discovery) and fin (finish) timestamps decide which class each edge falls into.

Same DFS tree, four edge classes: solid spine is tree, the orange loop is back, the dashed curve is forward, the gray curve is cross. An undirected DFS produces only tree and back edges - forward and cross cannot occur.

Name	Test when DFS first looks at u -> v
	Direction in the DFS tree / cycle?
Tree edge	v is WHITE (unseen) - you recurse into it
	down one level - not a cycle
Back edge	v is GRAY - still on the recursion stack
	up, to an ancestor - YES, a cycle
Forward edge	v is BLACK and disc[u] < disc[v]
	down, skipping levels, inside your own subtree - not a cycle
Cross edge	v is BLACK and disc[u] > disc[v]
	sideways, into a finished sibling subtree - not a cycle

⚠

Edge names describe the DFS run, not the graph

These four names describe a DFS run, not the graph. Start the same DFS at a different vertex and edges swap classes - what was a cross edge becomes a tree edge, and so on. The only class-membership fact that is graph-level is the important one: a directed graph has a cycle if and only if some DFS finds a back edge, and that holds no matter where you start. Anything you conclude from "this is a cross edge" is a statement about your traversal.

⚠

"Normal edge" isn't a real term

"Normal edge" is not a term - and the thing people usually mean by it is "tree edge." There is no fifth class. Any edge a DFS examines lands in exactly one of the four above, because the target vertex is WHITE, GRAY, or BLACK, and BLACK splits on the timestamp comparison. If you find yourself needing a fifth name, you are describing a role (below), not a DFS class.

The full derivation - including why undirected DFS cannot produce forward or cross edges, and how the timestamps power low-link algorithms - is in Cycles & Ordering, section 3.

Role-in-an-answer edge types

These have nothing to do with the graph's shape or a DFS run. Each one describes whether an edge got picked by some algorithm, and picked relative to what - the same edge can be an MST edge under one run of Kruskal's and just an ordinary edge under another, tied-weight run.

Name	Definition
	Why it matters
MST edge	an edge Kruskal's or Prim's included in one particular computed MST
	Only defined relative to a chosen MST - a graph with tied edge weights can have several valid MSTs that disagree on which edges are MST edges. See Minimum spanning trees.
Redundant edge	the edge a union-find union call returns False on - it closes a cycle instead of merging two components
	The entire answer to LC 684 Redundant Connection: keep every edge whose union call returns True, report the first one that returns False. See Cycles & Ordering, section 9.
Critical edge	an edge that lies in every MST - removing it strictly increases the cheapest possible spanning tree's weight
	LC 1489 Find Critical and Pseudo-Critical Edges tests this by re-running Kruskal's with the edge excluded (critical, if the MST gets worse or disconnects) and forced in first (pseudo-critical, if that still matches the true MST weight). Confusingly, this site also uses "critical edge" for a bridge in the single-point-of-failure sense (see Structural edge types) - same words, unrelated meaning.
Matching edge	an edge belonging to a chosen matching - a set of edges no two of which share an endpoint
	What a matching is made of, the way a spanning tree is made of tree edges. See Flows & Matching, section 3.
Residual edge	an edge in the residual graph of a flow network - either unused forward capacity, or a reverse edge letting an algorithm undo flow it already sent
	What makes augmenting-path max flow provably correct: a greedy choice is never final while a residual edge can still take it back. See Flows & Matching, section 1.

Where to go next

• Representation - the three ways to store the graph you just learned to describe (adjacency list, matrix, edge list) and the index-vs-value bug that eats matrix code.
• Degree - the practice set that needs nothing from this page beyond section 2.