Graphs

Overview

A directed graph $G$ is a pair $⟨V,E⟩$, where $V$ is a finite set and $E$ is a binary relation on $V$. An undirected graph $G$ is a pair $⟨V,E⟩$, where $V$ is a finite set and $E$ is a set of unordered pair of vertices from $V$. In both types of graphs, $V$ is called the vertex set of $G$ and $E$ is called the edge set of $G$.

A graph that allows multiple edges between vertices is called a multigraph. It is analagous to the concept of multisets in set theory.

Incidence

If $⟨u,v⟩$ is an edge of a directed graph, we say $⟨u,v⟩$ is incident to $v$ and incident from $u$. Furthermore, we say $v$ is adjacent to $u$. If $\{u,v\}$ was instead an edge of an undirected graph, we say $\{u,v\}$ is incident on $u$ and $v$. Likewise, $v$ is adjacent to $u$ and $u$ is adjacent to $v$.

Handshake Lemma

In any graph, the sum of the degrees of vertices in the graph is always twice the number of edges: ${\sum }_{v\in V}d(v)=2e.$

Walks

Let $G=(V,E)$ be a graph. A walk of $G$ is a sequence of vertices such that consecutive vertices in the sequence are adjacent in $G$. More precisely, a walk (of length $k$) from vertex $v_0$ to vertex $v_k$ is a sequence $w=⟨v_0,v_1,\dots ,v_k⟩$ of vertices such that $(v_{i-1},v_i)\in E$ for $i=1,2,\dots ,k$. We say $v_k$ is reachable from $v_0$ via $w$.

Trails

A trail is a walk in which no edge is repeated.

Paths

A path is a trail in which no vertex is repeated (except possibly the first and last). A cycle is a path that starts and ends at the same vertex. A graph with no cycles is acyclic.

In computer science, a cycle is sometimes required to have more than one edge:

• In a directed graph, path $⟨v_0,v_1,\dots ,v_k⟩$ is a cycle if $v_0=v_k$ and the path contains at least one edge.
• In an undirected graph, path $⟨v_0,v_1,\dots ,v_k⟩$ is a cycle if $v_0=v_k$ and all edges are distinct.

Isomorphisms

An isomorphism between two graphs $G_1$ and $G_2$ is a bijection $f:V_1\to V_2$ between the vertices of the graphs such that $(a,b)$ is an edge in $G_1$ if and only if $(f(a),f(b))$ is an edge in $G_2$. Here parenthesis are used to denote either ordered pairs (for directed graphs) or unordered pairs (for undirected graphs).

We say $G_1$ and $G_2$ are isomorphic, denoted $G_1\cong G_2$, if and only if there exists an isomorphism between $G_1$ and $G_2$.

Subgraphs

We say $G^{\prime }=(V^{\prime },E^{\prime })$ is a subgraph of $G=(V,E)$ provided $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$. We say $G^{\prime }=(V^{\prime },E^{\prime })$ is an induced subgraph of $G=(V,E)$ provided $V^{\prime }\subseteq V$ and every edge in $E$ whose vertices are still in $V^{\prime }$ is also an edge in $E^{\prime }$.

Bibliography

• Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., n.d., https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf.
• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).