Graph Theory

Reference:
Introductory Combinatorics by Richard A. Brualdi, Chapter 11.

1. Numerous Definitions

$\textbf{Definition}$ of General Graph
A general graph $G$ is a pair $(V,E)$ where $V$ is a set of vertices and $E\subset V\times V$ is a multi-set of edges, where each edge is a two-element subset of $V$.

Note that in General Graph, the order of the two elements in an edge is not important. That is, $(u,v)$ and $(v,u)$ are the same edge.

$i.e.$, if $e\in E$ is of the form $\{u, v\}$, we say $e$ joins $u$ and $v$.

If $\exists e\in E,v\in V:e=\{v,v\}$, then we say $e$ is a loop.
If $\exists e_1,e_2\in E:e_1=e_2$, then we say $e_1$ and $e_2$ are multiple edges.

$\textbf{Definition}$ of Simple Graph
A simple graph $G$ is a general graph where there is no loop and no multiple edges between any two vertices.

Note: from now on, when we say graph, we mean simple graph.

$\textbf{Definition}$ of Complete Graph
A complete graph $K_n$ is a simple graph with $n$ vertices and an edge between every pair of distinct vertices.

If a vertex $v$ is an endpoint of an edge $e$, then we say $v$ is incident to $e$ (or $e$ is incident to $v$).

$\textbf{Definition}$ degree of a vertex
The degree of a vertex $v$ in a graph $G$ is the number of edges incident to $v$. We denote it by $\deg(v)$.

$\textbf{Theorem}$
Let $G=(V,E)$ be a graph, then

$$\sum_{v\in V}\deg(v)=2|E| $$

$Pf$: We use the double counting method.

$$\begin{aligned} &|\{(v,e)\in V\times E\mid v \text{ is incident to }e\}|\\ = &\sum_{e\in E}\sum_{\exists u\in V:e=\{u,v\}}1=\sum_{e\in E}2=2|E|\\ = &\sum_{v\in V}\sum_{\substack{\exists u\in V,e\in E\\e=\{u,v\}}}1=\sum_{v\in V}\deg(v)\\ \end{aligned} $$

$\textbf{Definition}$ of Walk, Trail and Path
A sequence of edges of form $e_1,e_2,\cdots,e_k$ is called a walk of length $k$ if

$$\forall i\in [1,k-1]:e_i\cap e_{i+1}\neq \emptyset $$

Then we denote $e_k$ by $e_k=\{v_{k-1},v_k\}$.
If all the edges in the walk are distinct, then we call it a trail.
If all the vertices in the walk are distinct, then we call it a path. By definition, a path is always a trail.

A path is called closed if $v_0=v_k$, and it is called open if $v_0\neq v_k$.

$\textbf{Definition}$ of Cycle
A cycle is a closed path.

$\textbf{Definition}$ of Connectedness
A graph $G$ is connected if for every pair of vertices $u,v\in V$, there is a walk from $u$ to $v$. A graph is disconnected if it is not connected.

$\textbf{Definition}$ of Distance
We define the distance between two vertices $u,v$ in a connected graph $G$ to be the length of the shortest path from $u$ to $v$. We denote it by $d(u,v)$. Specially if $u=v$, then $d(u,v)=0$.

$\textbf{Definition}$ of Subgraph
A graph $H=(V',E')$ is a subgraph of $G=(V,E)$ if $V'\subset V$ and $E'\subset E$.

注意这里 $H$ 首先是一个图, 然后才是 $G$ 的子图.

$\textbf{Definition}$ of Isomorphism
Two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there exists a bijection

$$\theta:V_1\xrightarrow{\cong} V_2 $$

that induces a bijection

$$\theta:E_1\xrightarrow{\cong} E_2\\ \{u,v\}\longmapsto \{\theta(u),\theta(v)\} $$

$\textbf{Definition}$ of Adjacency Matrix
The adjacency matrix of a graph $G=(V,E)$ is the $|V|\times |V|$ matrix $A$ where

$$A_{ij}=\left\{ \begin{aligned} &1, \{v_i,v_j\}\in E\\ &0, \{v_i,v_j\}\notin E \end{aligned} \right. $$

Specially since $G$ is simple, $A_{ii}=0$.

2. Euler Trails & Euler Cycle

Königsberg bridge problem is the first problem in graph theory. The question is: can you walk through the city of Königsberg and cross each bridge exactly once?

The answer is no.

3. Hamiltonian Cycle

4. Bipartite Graph

$\textbf{Definition}$: A graph $G=(V,E)$ is bipartite if $V$ can be partitioned into two nonempty sets $V_1$ and $V_2$ such that

$$V = V_1\sqcup V_2 $$

and

$$E\subset V_1\times V_2 $$

$\textbf{Example}$: The complete bipartite graph $K_{m,n}$ is a bipartite graph with $m$ vertices in $V_1$ and $n$ vertices in $V_2$ and an edge between every pair of vertices in $V_1$ and $V_2$.

5. Trees