# Graph Theory

Learned formally in MATH239. See Graph for implementation for a programming perspective.

Relationship with Combinatorics

I learned graph theory in my combinatorics course, and although it seems like they are completely different, I think itβs because graphs also involve counting: number of paths between nodes, number of subgraphs, ways to color a graph, etc.

### Concepts

#### Graph Density

The average degree of a vertex in $G$ is $β£V(G)β£2β£E(G)β£β$ This is a measure of the density of a graph.

#### Girth

The *girth* of a graph is the length of its shortest cycle. If $G$ has no cycle, then its girth is $β$.

#### Subgraph

A graph $H$ is a *subgraph* of a graph $G$ if the vertex set of $H$ is a (non-empty) subset of the vertex set of $G$ ($V(H)βV(G)$) and the edge of $H$ is a subset of the edge set of $G$ ($E(H)βE(G)$) where both endpoints of any edge in $E(H)$ are in $V(H)$.

- If $V(H)=V(G)$, we call $H$ a
**spanning subgraph** - If $Hξ=G$, then $H$ is a
**proper subgraph**

#### Walk

A $u,v$-*walk* is a sequence of alternating vertices and edges $v_{0},v_{0}v_{1},v_{1},v_{1}v_{2},v_{2},...,v_{kβ1},v_{kβ1}v_{k},v_{k}$ where $u=v_{0}$ and $v=v_{k}$. This walk has length $k$.

- a walk is
**closed**if $v_{0}=v_{k}$

#### Path (also called simple path)

A $u,v$-*path* is a $u,v$-walk with no repeated vertices.

- Note that since no vertices are repeated, no edges are repeated either

Theorem 4.6.2

If there is a $u,v$-walk in $G$, then there is a $u,v$-path in $G$.

Corollary 4.6.3

If there is a $u,v$-path and a $v,w$-path in $G$, then there is a $u,w$-path in $G$.

#### Cycle

A *cycle* of length $n$ is a subgraph with $n$ distinct vertices $v_{0},v_{1},...,v_{nβ1}$ and $n$
distinct edges $v_{0}v_{1},v_{1}v_{2},...,v_{nβ2}v_{nβ1},v_{nβ1}v_{0}$.

- In a simple graph, the minimum length of a cycle is 3 (the triangle)

Theorem 4.6.4

If every vertex in $G$ has degree at least 2, then $G$ contains a cycle.

#### Bridge

An edge $e$ of $G$ is a bridge (or cut-edge) if $Gβe$ has more components than $G$.

Lemma 4.10.2

If $e=xy$ is a bridge in a connected graph $G$, then $Gβe$ has exactly 2 components, and $x$ and $y$ are in different components of $Gβe$.

Theorem 4.10.3

An edge $e$ is a bridge of $G$ if and only if it is not contained in any cycle of $G$.

This fully characterizes bridges:

- edge in cycle $βΊ$ edge is not a bridge
- edge not in cycle $βΊ$ edge is a bridge

### Types of Graphs

- Planar Graph
- Petersen Graph
- k-Regular Graph
- Complete Graph
- Bipartite Graph
- Interference Graph
- Connected Graph

Visualization