1 Graphs

Definition

Let $G=(V,E)$ be a graph. Then:

• $E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$: normal graph
• $E\subseteq V\times V$: directed graph

Definition

A graph is called planar if it can be drawn in the plane such that no two edges (that is, the line segments or arcs representing the edges) cross.

A graph without loops and multiple edges is called simple.

Convention. All our graphs are simple.

Examples.

• complete graph $K_n$
• bipartite graph $G=(V_1,V_2,E)$
• $k$-partite graphs and complete $k$-partite graphs
• the hypercube $Q_n$: $V(Q_n)=\{0,1{\}}^n$, where $\{x,y\}\in \left(\genfrac{}{}{0ex}{}{V}{2}\right)$ iff $x_i\ne y_i$ for exactly one position.
• path of length $n$ $P_n$
• cycle $C_n$
• Petersen graph: SRG $(10,3,0,1)$
• $\overline{G}$ complement of $G$: for example, $P_4=\overline{P_4}$ is self-complmentary
• isomorphic graph:
  • Graph Isomorphism Problem (GI): Babai, Helfgott, quasi-polynomial time
  • Practical Graph Isomorphism Problem
    • 1990s: solved (Brendan McKay)
    • 2000s: not solved
• subgraph and induces subgraph ($E^{\prime }=E\cap \left(\genfrac{}{}{0ex}{}{V^{\prime }}{2}\right)$)

Proposition

Let $G=(V,E)$. Then ${\sum }_{x\in V}\mathrm{deg}(x)=2|E|$.

Theorem

A finite graph with odd valency has an even number of vertices.

Representations of Graphs

Definition

Let $G=(V,E)$ with $V=\{v_1,\cdots ,v_n\}$ and $E=\{e_1,\cdots ,e_m\}$. Define adjacency matrix $A=(a_{ij})$ as

$$a_{ij}=\{\begin{array}{ll}1& \text{if }{v}_i\sim v_j,\\ 0.& \text{otherwise}.\end{array}$$

Define incidence matrix $B=(b_{ij}{)}_{n\times m}$ as

$$b_{ij}=\{\begin{array}{ll}1& \text{if }{v}_i\in e_j,\\ 0& \text{otherwise}.\end{array}$$

Define degree matrix $D=(d_{ij})$ with $d_{ii}={\delta }_{ij}\mathrm{deg}(v_i)$.

Define Laplacian matrix $L=D-A$.

Convention. Let $A=(a_{ij}{)}_{n\times n}$ be an adjacency matrix. For us, we assume that $A\in {\mathbb{R}}^{n\times n}$ (sometimes $A\in {\mathbb{C}}^{n\times n}$). Only important in spectral graph theory.

Exercise. $B{B}^T=D+A$

Definition

A walk in a graph $G$ consists of an alternating sequence

$$x_0,e_1,x_1,e_2,x_2,\dots ,x_{k-1},e_k,x_k$$

of vertices $x_i$, not necessarily distinct, and edges $e_i$ so that the ends of $e_i$ are exactly $x_{i-1}$ and $x_i,i=1,2,\dots ,k$. Such a walk has length $k$.

If the edge terms $e_1,\dots ,e_k$ are distinct, then the walk is called a path from $x_0$ to $x_k$. If $x_0=x_k$, then a walk (or path) is called closed. A simple path is one in which the vertex terms $x_0,x_1,\dots ,x_k$ are also distinct, although we say we have a simple closed path when $k\ge 1$ and all vertex terms are distinct except $x_0=x_k$.

Eulerian Circuit and Hamiltonian Circuit

Definition

A closed path through a graph using every edge once is called an Eulerian circuit and a graph that has such a path is called an Eulerian graph.

Theorem

A finite graph $G$ with no isolated vertices (but possibly with multiple edges) is Eulerian if and only if it is connected and every vertex has even degree.

\begin{proof} One direction is easy.

To show that the conditions are sufficient, we start in a vertex $x$ and begin making a path. We keep going, never using the same edge twice, until we cannot go further. Since every vertex has even degree, this can only happen when we return to $x$ and all edges from $x$ have been used.

If there are unused edges, then we consider the subgraph formed by these edges. We use the same procedure on a component of this subgraph, producing a second closed path. If we start this second path in a point occurring in the first path, then the two paths can be combined to a longer closed path from $x$ to $x$. Therefore the longest of these paths uses all the edges. \end{proof}

Definition

A Hamiltonian circuit in a graph $G$ is a simple closed path that passes through each vertex exactly once (rather than each edge).

So a graph admits a Hamiltonian circuit if and only if it has a polygon as a spanning subgraph. In the mid-19th century, Sir William Rowan Hamilton tried to popularize the exercise of finding such a closed path in the graph of the dodecahedron (Fig. 1.9).

Remark. It is easy to decide whether a graph admits an Eulerian circuit. In contrast to this, the problem of deciding whether an arbitrary graph admits a Hamiltonian circuit is likely ‘intractable’. To be more precise, it has been proved to be NP-complete, see Garey and Johnson (1979).

However, in practice and under specific structural conditions, the problem frequently becomes “easy”. For example, if a graph $G$ satisfies $\mathrm{deg}(v)⩾n/2$ (for all $v\in V(G)$ with $n\ge 3$), it is guaranteed to be Hamiltonian (Dirac’s Theorem).