Intuition The one core ideaA graph is a picture of dots joined by lines . The incidence matrix is just a tick-grid — a table with one row per dot and one column per line — where you put a mark whenever "this dot touches this line". Everything on this page builds the vocabulary you need so that later, when precise symbols appear, you already see the picture behind each one.
Before you can trust the parent note Incidence matrix (parent) , you must own every piece of its vocabulary. We build them in order — each one uses only the ones above it.
A vertex is a single dot . It stands for one "thing": a person, a city, a webpage. We write vertices as v 1 , v 2 , v 3 , … name tag so we can tell dots apart.
The symbol v vertex . The subscript (the small number below) is a label, nothing more: v 2
Figure 1 — A single red dot labelled v 2
Intuition Why we need dots at allA computer cannot store "a city". But it can store "item number 2". Naming each thing v i
An edge is a line drawn between two dots. It means those two things are related (friends, connected roads, a link). We name edges e 1 , e 2 , …
An edge is defined by the pair of vertices it joins. We write e 1 = ( v 1 , v 2 ) v 1 v 2 v i
The word endpoint just means "a vertex sitting at the end of the line". Edge e 1 = ( v 1 , v 2 ) v 1 v 2
A graph G whole picture : the full set of dots plus the full set of lines. We write G
Figure 2 — Three red dots labelled 1, 2, 3 joined by three black lines into a triangle. Caption: a graph G n = 3 m = 3
That is all a graph is — dots and lines. The parent note's "triangle" is just three dots each joined to the other two.
Definition The two size numbers
n number of vertices (how many dots ).m number of edges (how many lines ).
These two letters run through the whole topic. Whenever you see n m n = 3 m = 3
Common mistake Don't mix them upn m different . A single line joining two dots gives n = 2 , m = 1
Definition Undirected vs directed edge
Undirected edge: a plain line — the relationship goes both ways ("Ali is friends with Beth" = "Beth is friends with Ali").Directed edge: an arrow — the relationship has a direction ("Ali follows Beth" is not the same as "Beth follows Ali").
Figure 3 — Top: two black dots joined by a plain line (undirected, both ways). Bottom: two black dots joined by a red arrow, with the start labelled "tail" and the arrowhead end labelled "head". Caption: an undirected edge is a plain line; a directed edge is an arrow with a tail and a head.
On a directed edge (an arrow), the dot the arrow leaves is the tail , and the dot it points into is the head . In the picture: the arrow starts at the tail and its arrowhead lands on the head — the words are literal.
Intuition Why direction forces a sign laterIf we only wrote "1 = connected", an arrow v 1 → v 2 v 2 → v 1 lose the direction. So the parent note uses − 1 + 1
Definition Out-degree and in-degreeOnce edges are arrows, one degree number is no longer enough — we split it in two:
Out-degree of a dot = how many arrows leave it (how many times it is a tail ).In-degree of a dot = how many arrows enter it (how many times it is a head ).
In the triangle-with-arrows v 1 → v 2 , v 2 → v 3 , v 1 → v 3 v 1 2 0 v 3 0 2 undirected incidence matrix (all marks positive) still row-sums to the total degree.
A self-loop is an edge whose two endpoints are the same dot — a line that leaves a dot and comes straight back to it, like v 1 → v 1
It is still an edge with "two endpoints", but both endpoints happen to be the same vertex. That is why, in the undirected incidence matrix, a loop touches its vertex twice and the entry becomes a 2
Intuition A self-loop in adirected graph
A self-loop is both the tail and the head at the same vertex — the arrow leaves and returns to the same dot. Under the tail-( − 1 ) ( + 1 ) cancel in the same cell : ( − 1 ) + ( + 1 ) = 0 0 Graph Laplacian are normally defined on loop-free graphs.)
Definition Parallel edges / multigraphParallel edges are two or more distinct lines joining the same pair of dots (imagine two separate roads both linking city v 1 v 2 multigraph .
Intuition What parallel edges look like in the tick-gridEach parallel edge is still a separate edge , so it gets its own column . If e 1 = ( v 1 , v 2 ) e 2 = ( v 1 , v 2 ) e 1 e 2 identical — both mark rows v 1 v 2 duplicate columns ), whereas a plain adjacency count would blur them together. The "exactly two marks per column" rule still holds — it is per edge , not per pair of dots .
Definition Degree of a vertexThe degree of a dot, written deg ( v i ) number of line-ends touching it — count how many lines poke into that dot.
Figure 4 — One central red dot labelled v v deg ( v ) = 3
Intuition Why "line-ends", not "lines"A self-loop touches its dot with both its ends, so it adds 2 to the degree. Counting ends (not whole edges) is what keeps the tidy rule "row-sum = Degree of a vertex .
The degree is exactly what a row of the incidence matrix will add up to. And adding up all degrees gives 2 m m Handshake Lemma .
A tick-grid is a plain table : one row for each vertex and one column for each edge . In the cell where a row and a column meet, you write a mark if that vertex touches that edge, and leave it blank (a 0 1 2 ± 1
For the triangle of Figure 2, the tick-grid (marks shown as 1
e 1 = ( v 1 , v 2 ) e 2 = ( v 2 , v 3 ) e 3 = ( v 1 , v 3 )
v 1 1
0
1
v 2 1
1
0
v 3 0
1
1
Read any column top-to-bottom: it has exactly two 1 1
A matrix is a rectangle of numbers arranged in rows (going across) and columns (going down). We name our incidence matrix B B in the older word "biadjacency", but just treat it as a name).
Definition The subscript addressB ij B ij row i , column j ". The first subscript is which row (which vertex), the second is which column (which edge). It is a grid reference, exactly like "row 3, seat 5" in a cinema.
n × m n × m n by m shape : n m n n m m Sparse graph representations for how big grids are stored efficiently.
B ij i j coordinates , not a product. B 23
Definition Sigma / summationj = 1 ∑ m B ij add up the numbers B i 1 , B i 2 , … , B im ∑ j = 1 starts ; the m stops .
Intuition Reading the row-sum aloud∑ j = 1 m B ij across row i m counts the touching edges — which is the degree. That is the whole proof of the parent's row-sum rule, in words.
The parent note ends with 1 T B = 0
A column vector is just a single column of numbers (a matrix that is one column wide). Think of it as a stack.
Definition The all-ones vector1 0
1 1 n = 3 1 1 1 0 0
T transpose , written with a small raised T flips a matrix on its side : rows become columns and columns become rows. So 1 1 T row of ones).
1 T B = 0 row of ones 1 T B B 1 T B = 0 every column of the directed incidence matrix sums to zero " — the tail ( − 1 ) ( + 1 ) Graph Laplacian .
The roadmap below reads top-down. Vertex (a dot) and edge (a line) are the two roots. An edge in turn carries three refinements: direction (tail/head), self-loops , and parallel edges . Vertex and edge together build the whole graph , which gives the two counts n m degree (line-ends at a dot), and direction splits degree into out-/in-degree . The counts fix the matrix shape and address B ij ; matrix + degree feed the summation (row-sum) idea; the matrix also feeds column vectors, transpose, 1 0 . All of these arrows finally converge on the incidence matrix itself.
Edge a line two endpoints
Parallel edges multigraph
Counts n dots and m lines
Degree ends touching a dot
Summation sigma add a row
Column vector transpose ones and zero
I can point to a vertex in a drawn graph and say why it's called v i A vertex is a dot; the subscript is just a name tag to tell dots apart.
I can state the unbreakable rule about how many endpoints an edge has Exactly two (a self-loop has both endpoints at the same dot).
I know what n m n m
I can explain the difference between an undirected and a directed edge Undirected = plain line, both ways; directed = arrow with a direction.
I can identify the tail and head of an arrow Tail = where the arrow leaves; head = where the arrowhead lands.
I can split a directed dot's degree into out-degree and in-degree Out-degree = arrows leaving (tails); in-degree = arrows entering (heads).
I can say why a self-loop adds 2 to a degree It touches its dot with both of its ends.
I can say what a self-loop does in a directed incidence matrix Its − 1 + 1 0
I know what parallel edges do to the incidence matrix Each is a separate edge with its own column, so they produce duplicate columns.
I can describe the tick-grid metaphor for the incidence matrix A table with one row per vertex, one column per edge, and a mark where a vertex touches an edge.
I can state the exact rule for an undirected entry B ij 1 v i e j 2 0
I can state the exact rule for a directed entry B ij − 1 + 1 0 0
I can read the address B ij The number in row i i j j
I can read ∑ j = 1 m B ij Add every entry across row i m
I know what n × m The shape of the matrix: n m
I can explain what 1 0 T 1 0 T
I can say what 1 T B = 0 Every column of the directed incidence matrix sums to zero.
