Graphs

Definition 2..1 (Graph)  

A graph is a pair $(V,E)$ with $E \subseteq V^{(2)}$.

Loops and multiple edges are forbidden.

Definition 2..2 (Vertices)  

$V=V(G)$ is the set of vertices of $G$.

Definition 2..3 (Edges)  

$E=E(G)$ is the set of edges of $G$.

Example 2..4 (Complete graph)  

$K_n$ is the complete graph on $n$ vertices (all ${n \choose 2}$ edges).

Example 2..5 (Cycle)  

$C_n$,$n \ge 3$ is a cycle of length $n$; it has vertices $v_1, v_2, \cdots, v_n$ and edges $v_1v_2, v_2v_3, \cdots$.

Definition 2..6 (Isomorphic graphs)  

Two graphs $G_1, G_2$ are isomorphic (symbol $\cong$) if there is a bijection $\phi: V(G_1) \rightarrow V(G_2): xy \in E(G_1) \Leftrightarrow \phi(x)\phi(y) \in E(G_2)$.

Definition 2..7 (Complement)   The complement of $G=(V,E)$ is $\bar{G} = (V, V^{(2)} \setminus E)$.

Example 2..8 ($C^5$ isomorphic to $\bar{C^5}$)  

Definition 2..9 (Subgraph)  

A subgraph of a graph $G$ is a graph $H$ with $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$.

Definition 2..10 (Induced subgraph)  

$H$ is an induced subgraph if $E(H) = E(G) \bigcap V^{(2)}(H)$. The induced subgraph with vertex set $W \subseteq V(G)$ is written $G[W]$.

Definition 2..11 (Spanning subgraph)  

$H$ is a spanning subgraph if $V(H) = V(G)$.

Definition 2..12 (Walk)  

A walk in a graph is a sequence of vertices $v_1,v_2,\cdots,v_k \in E(G) \forall 1 \le i < k$. Its length is $k-1$. It is closed if $v_1 = v_k$.

Definition 2..13 (Trail)  

A trail is a walk with no repeated edges.

Definition 2..14 (Euler trail/circuit)   An Euler trail/circuit is a trail or circuit which passes through all the edges.

Definition 2..15 (Eulerian)   A graph is Eulerian if it has an Euler circuit.

Definition 2..16 (Path)  

A path is a walk (a trail) with no repeated vertices.

Definition 2..17 (Cycle)  

A cycle is a closed walk of length $\ge 3$ with distinct vertices except that the frist and last are equal (isomorphic to $C_n$).

Definition 2..18 (Hamilton trail/circuit)  

A Hamilton path/cycle is a path/cycle which goes through every vertex of the graph.

Definition 2..19 (Hamiltonian)  

A graph is Hamiltonian if it has a Hamilton cycle.

Definition 2..20 (Neighbours of a vertex)  

Let $x$ be a vertex of $G$, its neighbours or adjacent vertices are $\Gamma(x) = \{ y \in V(G): xy \in E(G) \}$.

Definition 2..21 (Degree of a vertex)  

The degree of a vertex $x$ is $d(x) = \left\Vert\Gamma(x)\right\Vert$.

Definition 2..22 (Degree sequence of a graph)  

The degree sequence of a graph is a graph with vertices $v_1,\cdots,v_n$ is $d(v_1),\cdots,d(v_n)$.

Definition 2..23 (Maximum, minimum degree)  

The minimum/maximum degree of a vertex of $G$ is denoted $\delta(G)$ or $\Delta(G)$ respectively.

Definition 2..24 (Regular)  

A graph $G$ is regular if $\delta(G) = \Delta(G)$.

Definition 2..25 (Size of a graph)  

$e(G) = \left\Vert E(G)\right\Vert$ is the number of edges of $G$, its size.

Definition 2..26 (Order of a graph)  

$\left\Vert G\right\Vert = \left\Vert V(G)\right\Vert$ is the number of edges of $G$, its order.

Lemma 2..27 (Handshaking lemma)  

$\sum_{v \in V(G)} d(v) = 2e(G)$

Proof. Double count $\{ (x,xy) : x \in V(G), xy \in E(g) \}$.

$\qedsymbol$

Observation 2..28  

To solve problems try induction (on vertices, edges, and other things), try double counting (counting something in more than one way), consider the pigeon hole principle and consider extreme cases.

Definition 2..29 (Connected)  

A graph is connected if every pair of vertices is joined by a path.

The relationship on $V(G)$ where $x \sim y$ where is a path between $x$ and $y$ is an equivalence relation. The equivalence classes are called components of $G$.

Definition 2..30 (Acyclic)  

A graph is acyclic if it has no cycles.

Definition 2..31 (Tree)  

A tree is a connected acyclic graph.

Definition 2..32 (Forest)  

A forest is an acycle graph.

Theorem 2..33 (Properties of a tree)  

The following are equivalent

1. $G$ is a tree (connected, acyclic)
2. $G$ is minimal connected
3. $G$ is maximal acyclic

Proof. i $\implies$ ii. Let $G$ be connected and acyclic. Let $uv \in E(G)$. If $G - uv$ were connected then any $u-v$ path in $G - uv$ would give a cycle in $G$.

ii $\implies$ i. If $C$ were a cycle in $G$ and $uv \in E(G)$ then any $x-y$ path in $G$ passing via $uv$ could be patched up to $C-uv$ to give a path in $G - uv$. Contradiction.

i $\implies$ iii. Let $uv \notin E(G)$. Since $G$ connected $\exists u-v$ path in $G$ so there is a cycle in $G+uv$. Contradiction.

iii $\implies$ i. Suppose $G$ is not connected. Let $u,v$ be vertices of $G$ belonging to different components. $G+uv$ contains no cycles. Contradiction.

$\qedsymbol$

Corollary 2..34  

A graph is connected iff it has a spanning tree (i.e. $G$ has a subgroup $T$, $T$ a tree and $V(T)=V(G)$).

Proof. Assume $G$ has a spanning tree $T$. Then there is a path in $T$ and so in $G$ between all vertices.

Let $T$ be minimal connected spanning subgraph of $G$. By previous theorem it is a tree.

$\qedsymbol$

Definition 2..35 (Leaf)  

A leaf is a vertex $v$ with $d(v)=1$.

Lemma 2..36 (Trees have leaves)  

Every tree $T$ of order $n \ge 2$ has at least two leaves.

Proof. Let $P = x_1 \cdots x_k$ be a path of maximal length in $T$. Then $\Gamma(x_1) \subset P$, since $P$ is maximal. $T$ is acyclic so $\Gamma(x_1) \cap P = \{ x_2 \}$. Similarly for $x_k$.

$\qedsymbol$

Theorem 2..37 (Size of a tree)  

A tree of order $n$ has size $n-1$. $e(T) = \left\Vert T\right\Vert - 1$. (In fact a connected graph $G$ with $e(T) = \left\Vert T\right\Vert - 1$ is a tree, exercise.)

Proof. By induction on $n$. Clearly true for $n \le 2$. Let $T$ be a tree of order $n$ and let $v \in V(T)$ be a leaf. Let $x,y$ be vertices of $T-v$. There is an $x-y$ path in $T$. So $T$ connected implies $T-v$ connected so $T-v$ is a tree. By induction $e(T-v) = n-2 \implies e(T) = e(T-v)+1 = n-1$.

$\qedsymbol$

Observation 2..38 (Number of possible graphs)  

If vertices are labelled $1,\cdots,n$ there are $n \choose 2$ possible edges and each subset gives a graph so there are $2^{n \choose 2}$ possible graphs. If the vertices are unlabelled then each graph can be labelled in at most $n!$ possible ways. So there are at least $\frac{2^{n \choose 2}}{n!}$ graphs.

Theorem 2..39 (Cayley)  

There are $n^{n-2}$ labelled trees of order $n$.

Proof. (Due to Prüfer.) Given a labelled tree we constract a sequence of $n-2$ numbers in the range $1,\cdots,n$ as follows.

Select the lowest labelled leaf. Write down its neighbour. Delete the leaf. Repeat until just two vertices remain. Now have a function $f$ from set of labelled trees of order $n$ to $\{ 1, \cdots n \}^{n-2}$.

Claim: $f$ is injective. Each vertex $v$ appears $d(v)-1$ times in the sequence. Leaves are vertices not appearing. Given a sequence $(a_1,\cdots,a_{n-2})$ let $v_1$ be the least vertex not appearing, join it to $a_1$. Let $v_2$ be the least vertex not appearing in the new sequence $(v_1,a_2,\cdots,a_{n-2})$, join it to $a_2$. Repeat until there are only two nodes not in $(v_1,\cdots,v_{n-2})$, join them together. The original graph is reconstructed.

Claim: $f$ is surjective. Every sequence produces a connected acyclic graph $G$ with $e(G) = \left\Vert G\right\Vert - 1$ which must be a tree (or else add more edges to make a tree and produce a contradiction).

Deduce that $f$ is a bijection.

$\qedsymbol$

Definition 2..40 (Bipartite)  

A graph is bipartite with vertex classes $X,Y$ if $X$ and $Y$ partition $V(G)$ and no edge of $G$ lies within $X$ or $Y$ (every edge goes between them). We say that $X$ and $Y$ are independent sets. We sometimes think of colouring $X$ red and $Y$ blue.

Theorem 2..41 (König)  

A graph is bipartite iff it contains no odd cycles.

Proof. Any cycle alternates between the two vertex classes, so has even length.

We may suppose that the graph $G$ is connected, since a graph is bipartite if its components are bipartite.

Let the distance $d(u,v)$ between $u,v \in V(G)$ be the length of the shortest $u-v$ path. Let $u \in V(G)$. Define $U_i = \{ v \in V(G) : d(u,v) = i \}$ for $i = 0,1,2,\cdots$.

Note that an edge of $G$ can join vertices in $U_i$ and $U_j$ only if $j = i$ or $j = i + 1$ or $j = i - 1$.

Claim. There is no edge between vertices in $U_i$. Proof. If $yy' \in E(G): y,y' \in U_i$ then select paths $u-y$ and $u-y'$ of length $i$. Let $w$ be the last common vertex. Then $w-y$,$w-y'$ and $yy'$ form a cycle of length $2(i - d(u,w)) + 1$ contradicting absence of odd cycles.

Colour $U_0 \bigcup U_2 \bigcup U_4 \bigcup \cdots$ red and $U_1 \bigcup U_3 \bigcup U_5 \bigcup \cdots$ blue to give a bipartition of $G$.

$\qedsymbol$

Definition 2..42 (Complete bipartite graph $K_{m,n}$)  

$K_{m,n}$ is the complete bipartite graph with vertex classes of order $m$ and $n$ with all $mn$ edges.

Definition 2..43 (Planar graphs)  

A graph that can be drawn in the plane without crossings is planar. A graph drawn in the plane is a plane graph.

Definition 2..44 (Face or country)  

If we omit (``cut out'') the vertices and edges of a plane graph from the plane the remainder falls into connected components called faces or countries.

Theorem 2..45 (Euler)  

Let $G$ be a connected plane graph with $n$ vertices, $e$ edges and $f$ faces. Then $n - e + f = 2$.

Proof. By induction on $e = e(G)$. If $e = n-1$ then $G$ is a tree and $f = 1$. Done.

If $e > n-1$ there is a cycle $C$ in $G$. Then any $xy \in E(C)$ separates two different faces. Apply induction to $G - xy$ gives $n - (e-1) + (f-1) = 2$.

$\qedsymbol$

Observation 2..46  

It is convenient to use stereographic projection to consider a plane graph as drawn on the sphere. Then $G$ is connected iff all the faces are simply connected (homeomorphic to the unit disc).

Definition 2..47 (Bridge)  

A bridge in a plane graph is an edge whose removal increases the number of components.

Definition 2..48 (Bridgeless)  

In a bridgeless plane graph every edge separates two different faces.

$2e(G) = \sum_i {i f_i}$ where $f_i$ is the number of $i$-sided faces.

Definition 2..49 (Girth)  

The girth of a graph $G$ is the length of the shortest cycle.

Theorem 2..50 (Bound for number of edges in a planar graph)  

Let $G$ be a bridgeless plane graph with $n$ vertices and girth $g$. Then $e(G) \le \frac{g}{g - 2} (n-2)$. In particular a plane graph has at most $3n - 6$ edges.

Proof. Add edges if necessary to ensure that $G$ is connected. It remains bridgeless and planar. Then $2e = \sum_i i f_i \ge g \sum_i f_i = gf$. So $f \le \frac{2e}{g}$.

By Euler's theorem $n-2=e-f$. But $e -f \ge e - \frac{2e}{g} = \frac{g -2}{g} e \implies e \le \frac{g}{g - 2} (n-2)$.

$\qedsymbol$

Theorem 2..51 (Kuratowski (unproved))  

Kuratowski showed that the only non-planar graphs are those that contain a subdivision of $K_5$ or $K_{3,3}$ obtained by replacing edges with paths.

Theorem 2..52 (Eulerian condition)  

A graph is Eulerian iff it is connected and every vertex has even degree.

Proof. If the graph is Eulerian it must be connected. If a vertex has odd degree the path must pass in a different number of times from that which it passes out.

By induction on the number of edges. True for the empty graph. Since $\delta(G) \ge 2$ there are no leaves so $G$ is not a tree. Therefore $G$ must contain a cycle $C$. Each component of $G \setminus E(C)$ has vertices of even degree, so by induction hypothesis each has an Euler circuit. By traversing $C$ take time out to traverse each of these circuits when first encountered. We produce an Euler circuit for $G$ as $G$ is connected.

$\qedsymbol$

Corollary 2..53  

A connected graph $G$ has an Euler trail from a vertex $x$ to a vertex $y \ne x$ iff $x$ and $y$ are the only vertices of odd degree.

Proof. If there is an Euler trail then obvious.

If $x$ and $y$ are the only vertices of odd degree then form $G'$ by adding a new vertex $u$ and joining it to $x$ and $y$. By the theorem $G'$ has an Euler circuit. Deleting $u$ gives an Euler trail from $x$ to $y$.

$\qedsymbol$