Edge Types

A loop is an edge whose endpoints are equal.
Multiple Edges are edges that have the same pair of incident vertices
A graph is simple if it has no loops or multiple edges.
A graph is undirected if , then so is .

That is, we do not distinguish between the order of vertices listed in each edge. Otherwise, if there is a notion of direction, we say the graph is directed.
- For directed graphs, we refer to edges as arcs and the arc set is notated
A graph is weighted wherein each edge is assigned a value called its weight.

We may denote the weight of an edge as .

We may also denote the weight of a weighted graph as , that is the sum of weights of all its edges

Vertices

If , we say that is adjacent to . Denoted as . This is the adjacency relation.
We say that is incident to the vertices . This is the incidence relation.
The degree of a vertex denotes the number of edges that are incident to it. This is denoted
- The minimum degree is denoted
- The maximum degree is denoted
For a directed graph, we have:
- The out-degree of a vertex as the number of arcs coming from (that is, arcs of the form ). This is denoted
- The in-degree of as the number of arcs coming to (that is, arcs of the form ). This is denoted
- The degree of a vertex in the digraph is the number of arcs incident to it. It is therefore calculated as

Let be an undirected graph. A degree sequence is a monotonic non-increasing sequence of the vertex degrees of its graph vertices.
Handshaking Lemma. In an undirected graph, there must exist an even number of odd degree vertices.
Degree Sum Formula (Undirected)
Degree Sum Formula (Directed)

An isomorphism from to is a bijection such that if , then .
- We say that if an isomorphism between and exists, then the two graphs are isomorphic, which we denote as .
- Isomorphism is an equivalence class
- Adjacency is preserved under isomorphism.
The graph is a subgraph of a graph , denoted as if and only if and . We refer to as the supergraph
- If , we say that is a spanning subgraph of .
Let be any subset of vertices of . The induced subgraph, denoted is the graph whose vertex set is and whose edge set consists of all the edges in that have endpoints in . More formally, for ,
Two graphs are disjoint if they do not share any vertices.
Matrices in Graph Theory