Graph Routes

Definition 2.1

• A walk is a sequence of vertices so that there is an edge between consecutive vertices. A walk can repeat vertices and edges.
• A trail is a walk with no repeated edges. A trail can repeat vertices but not edges.
• A path is a trail with no repeated vertex (or edges). A path on n vertices is denoted $P_{n}$.
• A closed walk is a walk that starts and ends at the same vertex.
• A circuit is a closed trail; that is, a trail that starts and ends at the same vertex with no repeated edges though.
• A cycle is a closed path; that is, a path that starts and ends at the same vertex. Thus cycles cannot repeat edges or vertices. A cycle on n vertices is denoted $C_{n}$.

The length of tours = number of edges.

Definition 2.2

• Let $G$ be a graph. Two vertices x and y are connected if there exists a path from x to y in $G$. The graph $G$ is connected if every pair of distinct vertices is connected.

Theorem 2.3

• Every $x-y$ walk contains an $x-y$ path.
  • Proof:
    Prove this by induction. Suppose $l$ be the length of ab $x-y$ walk $W$.
    When $l=0$, then the walk does not have any vertices and edges so it contains a single vertex, that is $x=y and so$W$is a path of length 0.$ Supppose $l \ge 0$ and the claim holds for true for all $k \lt l$. If $W$ has no repeated vertex, then it cannot have any repeated edges and so $W$ is an $x-y$ path. Otherwise $W$ has a repeated vertex, call it $u$. We can remove all edges and vertices between two appearances of $u$ in the ealk, and leave only one copy of $u$. This will produce a shorter $x-y$ walk $W'$ which is contained in $W$. Thus, by the induction hypothesis we know $W'$ contains an $x-y$ path $P$, which is also contained in $W$. Thus $W$ contains an $x-y$ path $P$.

Definition 2.4

• An object $X$ is maximum if it is the largest among all objects under consideration; that is, $|X| \ge |A| \forall A \in \mathcal{U}$. An object $X$ is maximal if it cannot be made larger.

Theorem 2.5

• If every vertex of a graph has degree at least 2 than $G$ contains a cycle.

Eulerian Graphs

Definition 2.6

• Eulerian circuit is a circuit that contains every edge and every vertex of graph $G$.

Theorem 2.7

• A graph $G$ is eulerian $\iff$ $G$ is connected and every vertex has even degree.
  • Proof:
  1. $(\implies)$
     $G$ is eulerian.
     $\implies$ There is a circuit $C$ containing every edge and vertex of $G$.
     $\implies$ $G$ is connected.
     The circuit $C$ is a trail that starts and ends at the same vertex.
     $\implies$ For every vertex, there at least exists a pair of edges in and out.
     $\implies$ Every vertex has even degree. $\implies$ $G$ is connected and every vertex has even degree.
  2. $(\impliedby)$
     The proof processed by induction. Suppose $G$ has $m > 0$ edges and that for all $k$, with $m > k \ge 0$ that any connected graph $G'$ with $k$ edges and all vertices of even degree have an eulerian circuit.
     
     By Theorem 2.5, all vertices in $G$ have at least degree 2, then $G$ contains a cycle $C$. Let $G'$ be the graph obtained by deleting all the edge of $C$. $G'$ has less edges than $G$, thus it contains an eulerian circuit. To find the eulerian circuit of $G$, we traverse $C$ but when a component of $G'$ is encountered, we detour along its eulerian circuit. This detour will start and end at the same vertex, and we continue traversing $C$ until all edges being traveled, thus completing an eulerian circuit of $G$.
     

Algorithm for finding Eulerian circuit

Fleury’s Algorithm

• Given a graph $G$ where zero or two vertices are odd. If $G$ has no odd vertices, then any vertex can be teh starting point. If $G$ has odd vertices, then the starting point must be one of the odd vertices. From the starting point, using dfs travel through all edge and label the edge have been traveled. Then we have labeled eulerian circuit or trail. The complexity is the cost of doing dfs.

Hierholzer’s Algorithm

• Given a graph $G$ where all vertices are even.
  1. Select a starting vertex $v$, and find a circuit $C$ originating at $v$.
  2. Find any vertex $x$ on $C$ has edges not appearing in $C$, find a cicuit $C'$ originating at $x$.
  3. Combine $C$ and $C'$ into a single circuit $C*$.
  4. Repeat (2) and (3) until all edge of $G$ are used.

Hamiltonian Cycles

Definition 2.10

• Hamiltonian cycle is a cycle in a graph $G$ that contains every vertex of $G$.
• Hailtonian path is a path that contains every vertex.
• A graph that contains a hamiltonian cycle is called hamiltonian.

Properties of Hamiltonian Graphs

• $G$ must be connected.
• No vertex of $G$ have degree less than 2.
• $G$ cannot contain a **cut-vertex**, i.e. a vertex whose removal disconnects the graph.
• If $G$ contains a vertex $x$ of degree 2 then both edges incident to $x$ must be included in the cycle.
• If two edges incident to a vertex $x$ must be included in the cycle, then all other edges incident to $x$ cannot be used in the cycle.
• If in the process of attempting to build a hamiltonian cycle, a cycle is formed that does not span $G$, then $G$ cannot be hamiltonian.

Theorem 2.12 (Dirac’s Theorem)

• Let $G$ be a graph with $n \ge 3$ vertices. If every vertex of $G$ satisfies $deg(v) \ge \frac{n}{2}$, then $G$ has a hamiltonian cycle.
  • Proof: Noted that $G$ is connected. Let $P = x_{0}x_{1}...x_{n}$ be a path that contains all vertices in $G$. Let $S$ be the set of vertices that are adjacent to $x_{n}$ i.e. $S = \{x_{i}:x_{i}x_{n} \in E(G)\}$. Let $T$ be the set of vertices whise immediate neighbor on $P$ is adjacent to $x_{0}$ i.e. $T=\{x_{i}:x_{i+1}x_{0} \in E(G)\}$. Since both $x_{0}$ and $x_{n}$ have degree $\ge \frac{n}{2}$ we know $|S| + |T| \ge n$.
    Since $|S \cup T| \lt n$, thus $|S \cup T| = |S| + |T| - |S \cap T|$, then we have $|S \cap T| \ge 1$. There exists some vertex $x_{i}$ s.t. $x_{0}x+{i+1},x_{i}x_{n} \in E(G)$. Consider the cycle $C = x_{0} \underset{P}{-} x_{i}x_{n}\underset{P}{-}x_{i+1}x_{0}$, where $x \underset{P}{-}y$ indicates travaling from $x$ to $y$ along path $P$. Thus $C$ forms a hamiltonian cycle.
    

Theorem 2.13 (Ore’s Theorem)

• Let $G$ be a graph with $n \ge 3$ vertices. If $deg(x) + deg(y) \ge n$ for all distinct nonadjacent vertices, then $G$ has a hamiltonian cycle.

Definition 2.14

• The hamiltonian closure of a graph $G$, denoted $cl(G)$ is the graph obtained from $G$ by iteratively adding edges between pairs of nonadjacent vertices whose degree sum is at least $n$, that is we add an edge between $x$ and $y$ if $deg(x) + deg(y) \ge n$, until no such pair remains.

Theorem 2.16

• A graph $G$ is hamiltonian $\iff cl(G)$ is hamiltonian.

Lemma 2.17

• If $G$ is graph with at least 3 vertices such that its closure $cl(G)$ is complete, then $G$ is hamiltonian.

Theorem 2.18 (Posa’s Theorem)

• Let $G$ be a simple graph where the vertices have degree $d1,d2,...,dn$ such that $n \ge 3$ and the degrees are listed in increasing order. If for any $i \lt \frac{n}{2}$ either $d_{i} \gt i$ or $d_{n-i} \ge n-i$, then $G$ is hamiltonian.
  • Proof: We will $cl(G)$ is a complete graph, so by Lemma 2.17 we would know that both $cl(G)$ and $G$ are hamiltonian. Suppose for a contradiction that $cl(G)$ is not complete. Then there exist nonadjacent vertices $x$ and $y$ in $cl(G)$, and $deg_{cl(G)}(x) + deg_{cl(G)}(y) \le n-1$, as otherwise $xy$ would be added to $G$ in the formation of $cl(G)$. Choose $x$ and $y$ among all such nonadjacent pairs in $cl(G)$ so that the sum of their degrees in $cl(G)$ (TBD).

The Traveling Salesman Problem

Problem Statement

Given a weighted complete graph, find the hamiltonian cycle with least total weight.

Brute Force Algorithm

• Find all possible hamiltonian cycles and pich the one with smallest weight.
• Time Complexity: $n!$.

Nearest Neighbor Algorithm

• Always choose the least weight among adjacent node.
• Time complexity is $n^2$.
• Repetitive Nearest Neighbor Algorithm means considering every vertex as starting vertex and apply NN. This way may find more optimal solution.
• Approximate Algorithm with lower computation cost but not always optimal.

Cheapest Link Algorithm

• Repeat pick the one with the smallest weight among all edges with two conditions: (1) no vertex has three highlighted edges incident to it; (2) no edge is chosen so that a cycle closes before hitting all the vertices.
• Also an approximate algorithm. Generally perform well than NN.

Nearest Insertion Algorithm

1. First choose the smallest edge, hightlight the edge and its endpoints.
2. Pick a vertex which is cloest to the one of the two already chosen vertices,, highlight the new vertex and its edges to both previously chosen vertices.
3. Pick a vertex that is cloest to the one of the three chosen vertices. Calculate the increase in weight obtained by adding two new edges and deleting a previously chosen edge. Choose the scenario with the smallest total.
4. Repeat (3) until all vertices have been included.

Shortest Paths

Dijkstra’s Algorithm

• Given weighted connected simple graph $G=(V,E,w)$.

1. Let $u$ be the start vertex, and $L(x)$ means the shortest path from $u$ to $x$.
2. For the current vertex $u$, find the vertex $v$ with lowest weight and update

$L(v) = min(L(v), L(u) + w(uv))$. Let $u=v$;

3. Repeat step 2 until all vertex have been traveled.

• One source to many vertex. Timecomplexity: $O(nlog(n))$.

Theorem 2.24 Walks Using Matrices

Let $A$ be the adjacency matrix of graph $G$. $\forall n \gt 0, a_{ij}$ in $A^n$ counts the number of walks from $v_{i}$ to $v_{j}$ using n edges.

Definition 2.25

• distance: $d(x,y)$ is the shorest length from node $x$ to $y$.
• eccentricity: $\epsilon(x) = max_{y\in V(G)}d(x,y)$.
• diameter: maximum eccentricity among all vertices. $diam(G)=max_{x,y\in V(G)}d(x,y)$.
• radius: minimum eccentricity. $rad(G) = min_{x\in V(G)}\epsilon(x)$.

Theorem 2.26

• If $G$ is disconnected then $\bar{G}$ is connected and $diam(\bar{G}) \le 2$.
• Proof: We are going to prove that for any pairs of vertex $x$ and $y$, there is a $x-y$ path.
  1. For $xy \not\in E(G)$, then $xy \in E(\bar{G})$.
  2. For $xy \in E(G)$, then $x$ and $y$ are not adjacent in $E(\bar{G})$. $\exists z$ such that $z$ is in different component from $x$ and $y$
  $\implies xz,yz \in E(\bar{G}) \implies$ there is $x-y$ path in $G$.

Theorem 2.27

• For a simple graph $G$ if $rad(G) \ge 3$ then $rad(\bar{G}) \le 2$.

Theorem 2.28

• For any simple graph $G$, $rad(G) \le diam(G) \le 2rad(G)$.

Definition 2.29

Let $G$ be a graph with $rad(G) = r$. Central vertex is the vertex x which has $rad(x)=r$.

Definition

• girth: the minimul length of a cycle in $G$.
• circumference: the maximum length of a cycle.

Theorem 2.31

If $G$ is a graph with at least one cycle then $girth(G) \le 2diam(G)+1$.

• Proof note: use the property of shortest path.

Theorem 2.32

Let $G$ be a graph with $n$ vertices, radius at most $k$, and maximum degree at most $d$, with $d \ge 3$. Then $n < \frac{d}{d-2}(d-1)^k$.