Of Notes

Basic Graph Theory

3 min read · revised 15 October 2026 · referred to by 3 notes · ·

We build a graph with a set of vertices and edges where and .

For a given graph we can compute things like:

  • Order which is the number of vertices
  • Size which is the number of edges
  • Degree which is the number of adjacent vertices

Importantly we also differentiate a simple graph which does not have any self-edges from a network with self-edges and multi-edges.

On the notation of edges, it is common to denote an edge as in which the target node is the first in the parentheses.

Sub-graphs (induced)

A subgraph is any graph for which .

An induced subgraph however,

Definitions of Graphs

We have multiple notations and definitions of how to convey the shape of a graph… such as the matrix or set theoretic. Within these definitions we often talk about properties of graphs as-well:

  • Directed
  • Acyclic

Matrix Notation

This is the most basic notation of a graph which puts a one or zero where there is occurrence of an edge. We denote this matrix with where .

A rather simple example would be:

Where we only have two vertices and one edge.

Measuring Degrees

We leverage the Kronecker Delta Function to filter the matrix for properties we want.

Which give us the sum of the row essentially counting the number of 1s in that row.

For example the graph below, with edges , , , and , has (remembering that when the edge points ):

A directed graph on four vertices. Vertex \(3\) has two incoming edges, so \(k_{3}^{in} = 2\), the sum of row \(3\) of \(A\); the out-degree of vertex \(1\) is \(2\), the sum of column \(1\). Every other vertex has one edge in and one out, and both totals are \(M = 5\).
Fig. 1. A directed graph on four vertices. Vertex has two incoming edges, so , the sum of row of ; the out-degree of vertex is , the sum of column . Every other vertex has one edge in and one out, and both totals are .

Set Theoretic

This is a more interesting notation for when we want to understand the number of inward or outward edges of each vertex.

We start with to define a set of all vertices which have an edge pointing to our interest node.

From this we can then compute the in-degree by simply taking the size , and similarly for the out degree by reversing the order in the first term of the partial.

It also stands that:

Graph Structure Characteristics

We begin to concern ourselves with the structure of a given graph. We start by asking questions like:

How many paths are there to connect to of length ?

Assuming we have two nodes with two nodes between them such that such that

Which by a matrix identity:

where the general formula is .

The path \(3 \to j \to i \to 1\). Each arrow contributes one factor of \(A\), and summing the product over every choice of the two middle vertices \(j\) and \(i\) counts all such paths, which is the entry \((A^{3})_{13}\).
Fig. 2. The path . Each arrow contributes one factor of , and summing the product over every choice of the two middle vertices and counts all such paths, which is the entry .
/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card