Graphs

A graph can be expressed a $G = (V, E)$, where $V$ is the set of vertices (nodes) and $E$ is the collection of edges (arcs). $E$ is not necessarily a set because there may be two edges between the same two vertices. In a directed graph, an edge could be represented $(u,v) \in E$ where $u,v \in V$. Because the edge is directed, the order of the pair is important. In an undirected graph the order of the pair is unimportant.

Adjacency, incidence, degrees and the handshaking lemma

A vertex is adjacent to another if they are connected by an edge.

An edge is incident to a vertex is it is joining it. For example, the edge between two vertices $a$ and $b$ is incident to $a$ and incident to $b$.

The degree of a vertex is the number of edges incident to that vertex. Note that if a vertex has a loop, then the loop is counted twice. In a directed graph, the in-degree of a vertex is the number of edges going into a vertex. The out-degree is the number of edges going out if the vertex.

The handshaking lemma states that the total degree of vertices in a graph is double the number of edges. Because of this, it is also true that an undirected graph has an even number of vertices of odd degree, as the sum of the degrees needs to be divisible by 2 (as the number of edges is half the total degree).

Isomorphism

An isomorphic graph is the same graph drawn differently. Two simple graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, are isomorphic if there exists a bijective function $f$ which maps $V_1$ to $V_2$ such that $\forall u,v \in V_1, (u,v) \in E_1 \Leftrightarrow (f(u), f(v)) \in E_2$. This means that both graphs must have the same edges between vertices.

Important graphs and graph classes

A graph with no edges is an empty graph.
A graph where every vertex is adjacent to every other is a complete graph.

Graphs continued

Walks, paths, tours and cycles

A walk in a graph $G = (V,E)$ is a finite sequence $V_0, (V_0, V_1), (V_1), (V_1, V_2), V_2, ...$ where $V_n$ is a vertex and pairs of vertices represent edges.
A walk without repeated edges is a path. A simple path doesn't repeat any vertex.
A tour is a walk which starts and ends at the same vertex.
A tour is a cycle if there are no repeated edges. A simple cycle has no repeated vertices except the first/last one.

Moving along an edge from one vertex to another can be expressed as $V_i \to V_j$. To express multiple edges, you can use $V_0 \to^* V_n$. If a walk exists between $V_0$ and $V_n$, it can be said that $V_n$ is reachable from $V_0$.
In an undirected graph, if $u \to^* v$, then $v \to^* u$, as if there exists a walk from $u$ to $v$ then there exists a walk from $v$ to $u$. It is symmetric.
In a directed graph, vertices are mutually reachable if there is a walk between them in both directions.

Eulerian and Hamiltonian cycles

A cycle is Eulerian if it traverses every edge exactly once. A connected, undirected graph with even degree vertices and no isolated vertices has an Eulerian cycle.

A Hamiltonian cycle visits every vertex of a graph exactly once.

Planar graphs

A planar graph can be drawn without edges overlapping. If a graph is not planar, then it's subgraphs will not be planar either. If a subgraph is not planar, the whole graph will not be planar either.

Trees

Introduction

A tree is a connected graph with no cycles.

Spanning trees

A subgraph ($G' = (V, F)$) of a tree ($G = (V, E)$), is called a spanning tree if it contains every vertex of the tree and is itself a tree.
Removing an edge from a cycle will leave a connected graph.
Adding a new edge to a connected graph on the existing vertices will create a cycle.
Every connected graph has a spanning tree.

Rooted trees

A rooted tree has a distinct root vertex from which all other vertices are connected.