FIT1058 Foundations of Computing - Graph Theory Notes

Graph Theory I

Introduction

• Graphs are abstract models of networks used to represent systems with interacting components.
• Examples include social networks, molecules, maps, electronic circuits, transport networks, the web, communication networks, software systems, and timetabling requirements.
• Graphs consist of vertices (nodes) and edges (links) between pairs of vertices.
• Graphs are abstractions that capture the structure of interactions while omitting details about how these interactions work.
• Graph theory can be used to solve problems such as:
  • Identifying influential individuals or subcommunities in social networks.
  • Finding efficient routes between cities.
  • Embedding electronic circuits in silicon wafers without wire crossings.
  • Displaying computer networks with minimal edge crossings.
  • Determining possible train routes or exam timetables without clashes.
• This chapter introduces basic concepts, vertex degrees, paths, and cycles.

11.1 Basic Definitions

• A graph $G$ is a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a set of unordered pairs of elements of $V$ (edges).
• $V(G)$ denotes the set of vertices of graph $G$.
• $E(G)$ denotes the set of edges of graph $G$.
• An edge $e ∈ E$ between vertices $v, w ∈ V$ is the set ${v, w}$.
• Example graph $G = (V, E)$:
  • $V = {a, b, c, d, e, f, g}$
  • $E = {{a, b}, {a, c}, {b, c}, {c, d}, {f, g}}$
• Two vertices $v, w$ are adjacent if ${v, w} ∈ E$, denoted as $v ∼ w$. If they are not adjacent, $v \nsim w$.
• A neighbor of vertex $v$ is any vertex $w$ adjacent to $v$. The set of all neighbors of $v$ is the neighborhood of $v$.
• Endpoints (endvertices) of an edge ${v, w}$ are $v$ and $w$.
• A vertex $v$ is incident with an edge $e$ if $v$ is one of the vertices in $e$ (i.e., $e = {v, x}$ for some vertex $x$).
• Two edges ${v, w}$ and ${v, x}$ are incident with each other if they share a common vertex $v$ (with $w ≠ x$).
• A vertex is isolated if it is not incident with any edges (i.e., not adjacent to any other vertices).
• A vertex is a leaf if it is incident with exactly one edge.
• In the example graph in Figure 11.1:
  • Vertex $c$ is incident with edges ${a, c}, {b, c}, {c, d}$.
  • Edge ${a, c}$ has endpoints $a$ and $c$. It is incident with ${a, b}, {b, c}$, and ${c, d}$.
  • Edge ${f, g}$ is incident with vertices $f$ and $g$, but not with any other edges.
  • Vertex $e$ is isolated.
  • Vertices $d, f$, and $g$ are leaves.

11.2 Types of Graphs

• Simple Graphs adhere to these conditions:
  • No vertex is adjacent to itself (no loops).
  • No two edges have the same pair of endpoints (no multiple edges).
• Unless specified otherwise, graphs are assumed to be simple graphs.
• Broader classes of graphs relax these conditions:
  • Loops: Edges whose endpoints are identical, connecting a vertex to itself.
  • Multiple Edges (Parallel Edges): More than one edge between a pair of vertices.
• Weighted Graphs: Graphs with numbers assigned to each edge, representing length, size, or cost.
• Undirected Graphs: Edges have no direction; the order of vertices in an edge ${v, w}$ does not matter.
• Directed Graphs: Edges are ordered pairs $(v, w)$, representing a directed connection from vertex $v$ to vertex $w$. Directed edges are called arcs.
• Mixed/Hybrid Graphs: Graphs containing both directed and undirected edges.
• Focus on simple (undirected) graphs:
  • They are relatively simple.
  • They appear as special cases in most other classes of graphs.
  • They are widespread as models of practical situations.
  • They capture main computational issues that arise in more general classes of graphs.

11.3 Graphs and Relations

• Graphs are closely related to binary relations.
• Adjacency is a binary relation defined on the set of vertices of a graph.
• For undirected graphs, adjacency is a symmetric binary relation: if $v$ is adjacent to $w$, then $w$ is adjacent to $v$.
• Adjacency is irreflexive: no vertex is adjacent to itself.
• Simple graphs may be regarded as irreflexive symmetric binary relations.
• Every simple graph gives rise to an irreflexive symmetric relation via adjacency.
• Every irreflexive symmetric relation may be used to define a simple graph.
• Discarding irreflexivity allows loops.
• Discarding symmetry yields directed graphs.
• Discarding both results in a directed graph that may have loops but no multiple edges, allowing the reverse edge $(w, v)$ for an existing edge $(v, w)$.
• Any binary relation can be regarded as a directed graph, possibly with loops but no multiple edges.

11.4 Representing Graphs

• Graphs can be displayed as diagrams but formal symbolic representations are needed for large graphs and computer storage.
• Four main ways of representing graphs symbolically:

11.4.1 Edge List

• An edge list is a list of the edges in a graph.
• The order of edges typically does not matter.
• To completely represent a graph, specify both the vertex set and the edge set.
• An edge list does not necessarily group edges by shared vertices, which may be less efficient for some task

11.4.2 Adjacency Matrix

• The adjacency matrix of a graph $G$ is an $n × n$ array $A$ of bits, where $n$ is the number of vertices.
• Rows and columns correspond to vertices.
• The entry in the $v$-row and $w$-column of $A$ is:
  • 1, if $v ∼ w$
  • 0, if $v \nsim w$
• Entries represent the number of edges between two vertices (0 or 1 for simple graphs).
• Observations about the adjacency matrix:
  • The main diagonal entries are all 0 (no self-loops).
  • The matrix is symmetric about the main diagonal (for undirected graphs).
• The number of 1s in the $v$-row (or $v$-column) captures information about vertex $v$.
• The number of 1s in the entire adjacency matrix is twice the number of edges.
• The rules for adjacency matrices can be relaxed for wider classes of graphs, such as allowing loops that would turn some of the diagonal entries into 1s. For directed graphs, the entry in row $v$ and column $w$ need not equal the entry in row $w$ and column $v$.
• Mathematical operations on adjacency matrices can reveal aspects of graph structure and are used in some algorithmic problems.
• One virtue of the adjacency matrix is that you can efficiently test whether or not two given vertices are adjacent.
• The adjacency matrix takes the same amount of space regardless of how many edges the graph has.
• If dealing with sparse graphs, the adjacency matrix representation may take up too much space in memory.

11.4.3 Adjacency List

• An adjacency list specifies the vertices in some order and, for each vertex, provides a list of all adjacent vertices.
• For example, the graph $G$ in Figure 11.1 has the following adjacency list representation:
  • $a : b, c$
  • $b : a, c$
  • $c : a, b, d$
  • $d : c$
  • $e :$
  • $f : g$
  • $g : f$
• From the adjacency list, one can readily see that $c$ is adjacent to $a, b$, and $d$, the neighborhood of $c$ is ${a, b, d}$, $e$ has no neighbors, and the graph has three leaves: $d, f$, and $g$.
• This representation enables efficient searching of neighborhoods of vertices and is compact compared to the adjacency matrix.

11.4.4 Incidence Matrix

• The incidence matrix of a graph $G$ is an $m × n$ array $A$ of bits, where $m$ is the number of edges and $n$ is the number of vertices.
• Rows correspond to edges, and columns correspond to vertices.
• The entry in the $e$-row and $v$-column is:
  • 1, if $e$ is incident with $v$
  • 0, if $e$ is not incident with $v$
• As with the adjacency matrix, certain matrix operations can be done with it in order to study the graph.
• This representation is seldom used in computers, but is theoretically important.

11.5 Subgraphs

• A subgraph of a graph $G = (V, E)$ is a graph $F = (U, D)$ such that $U ⊆ V$ and $D ⊆ E$.
• $F ≤ G$ denotes that $F$ is a subgraph of $G$.
• A graph is a subgraph of itself: $G ≤ G$.
• $F$ is a proper subgraph of $G$ if $F ≤ G$ and $F ≠ G$, denoted as F < G.

11.6 Some Special Graphs

• The complete graph on $n$ vertices, denoted by $K_n$, has every pair of vertices joined by an edge.
• The null graph on $n$ vertices, denoted by $K_n$, has no edges.
• The path graph of length $n−1$, denoted by $P_{n−1}$, has $n$ vertices and $n−1$ edges such that vertices can be sequenced so that two vertices are adjacent if and only if they are consecutive in the sequence.
• The cycle of length $n$, denoted by $C_n$, has $n$ vertices and $n$ edges and is formed from a path graph by adding an edge between the first and last vertices of the path.

11.7 Degree

• The degree of a vertex is the number of neighbors it has, which is also the number of edges incident with the vertex (for simple graphs).
• $\text{deg}_G(v)$ denotes the degree of vertex $v$ in graph $G$. If the graph is clear from context, it may be written as $\text{deg}(v)$.
• A vertex is isolated if and only if it has degree 0.
• A vertex is a leaf if and only if it has degree 1.
• If $n$ is the number of vertices, the degrees can be any of $0, 1, 2, …, n − 1$.

Theorem 56

• In every graph, there are two vertices with the same degree.
• Proof by cases:
  • Case 1: If $G$ does not have a vertex of degree $n−1$, possible degrees are $0, 1, 2, …, n−2$. Since there are only $n−1$ different numbers in this list, but there are $n$ vertices, at least two must have the same degree.
  • Case 2: If $G$ has a vertex $v$ of degree $n−1$, then $v$ is adjacent to all other vertices. Therefore all other vertices have $v$ as a neighbor, so their degrees are all greater than or equal to 1. Thus, all the degrees of all the vertices of $G$ must be in the set ${1, 2,…,𝑛 − 1}$. This means there are only $n−1$ possible degrees that a vertex of $G$ can have. But there are $n$ vertices in $G$. Therefore there must be at least two vertices in $G$ that have the same degree.

Theorem 57 (Handshaking Lemma)

• For every graph $G = (V, E)$, the sum of the degrees of the vertices is twice its number of edges:
• $\sum_{v ∈ V} \text{deg}(v) = 2m$, where $m$ is the number of edges of $G$.
• Proof: Each edge contributes 1 to the degree of each of its two endpoints. Thus, each edge is counted twice when summing the degrees of all vertices.

Corollary 58

• For any graph $G$, average degree of $G = \frac{2m}{n}$, where $n$ is number of vertices and $m$ is number of edges.
• Proof: average degree of $G = \frac{\text{sum of degrees}}{\text{number of vertices}} = \frac{\sum_{v ∈ V(G)} \text{deg}(v)}{n} = \frac{2m}{n}$.
• The average degree can range from 0 (for a graph with no edges) to $n−1$ (for a complete graph on $n$ vertices).

Corollary 59

• Every graph has an even number of vertices of odd degree.
• Proof: The sum of all degrees is even (by Theorem 57). The sum of even degrees is even. Therefore, the sum of odd degrees must be even. The sum of an even number of odd numbers is even, while the sum of an odd number of odd numbers is odd. It follows that there must be an even number of odd degrees.

11.8 Moving Around

• A walk from vertex $v$ to vertex $w$ is a sequence of vertices and edges:
• $v<em>0, e</em>1, v<em>1, e</em>2, v<em>2, …, v</em>{k−1}, e<em>k, v</em>k$, where
  • $v_0 = v$ (starts at $v$)
  • $v_k = w$ (finishes at $w$)
  • each $v_i$ is a vertex of $G$
  • each $e_i$ is an edge of $G$
  • $∀i: e<em>i = {v</em>{i−1}, v<em>i}$ (edge $e</em>i$ links vertices $v<em>{i−1}$ and $v</em>i$)
• The length of a walk is the number of edges in it.
• The shortest possible walk is of length zero, consisting of a single vertex and no edges.
• Two freedoms in walking around a graph:
  • Vertices can be visited more than once.
  • Edges can be traversed more than once, possibly in different directions.
• For simple graphs, a walk can be specified by just listing the vertices in order:
  • $v = v<em>0, v</em>1, v<em>2, …, v</em>{k−1}, v_k = w$
• If the graph has multiple edges, specifying the edges is necessary.
• A walk is closed if its start and end vertices are the same (i.e., $v = w$).
• A trail is a walk in which no edge is used more than once.
• A closed trail is a closed walk that is also a trail.
• A path is a trail in which no vertex or edge is repeated.
• The distance between two vertices is the length of the shortest path between them.

Theorem 60

• Let $G$ be any graph. $G$ has an odd closed walk if and only if it has an odd cycle.
• Proof:
  • (⟹) If $G$ has an odd cycle, every cycle is a closed walk. So an odd closed cycle is an odd closed walk. Therefore $G$ has an odd closed walk.
  • (⟸) Suppose $G$ has an odd closed walk. Let $W$ be the shortest odd closed walk in $G$. The sequence of vertices of $W$ may be written as $v<em>0, v</em>1, v<em>2,…,v</em>{k−1}, v<em>k = v</em>0$, where $k$ is odd. If no vertex of $G$ except the start/end vertex repeats in $W$, then $W$ is already an odd cycle, and we are done. Assume, by way of contradiction, that there is a vertex that is repeated in $W$. Let $v<em>i$ be the first vertex in this shorter list that appears again later in the list as $v</em>j$. So $v<em>i = v</em>j$, and 0≤i<j≤k−1. Using the vertices $v<em>i$ and $v</em>j$, we can divide the closed walk $W$ into two shorter closed walks: $v<em>i, v</em>{i+1},…,v<em>{j−1}, v</em>j$ and $v<em>j, v</em>{j+1},…,v<em>{k−1}, v</em>0, v<em>1,…,v</em>{i−1}, v_i$. Recall that the length of $W$ is odd. Since we just divided $W$ into two “subwalks”, the length of $W$ must equal the sum of the lengths of those two subwalks. Therefore, one of those subwalks has odd length and the other has even length. Both are closed walks, so the one that has odd length is an odd closed walk. Since both the subwalks are shorter than $W$, we have constructed an odd closed walk in $G$ that is shorter than $W$.
• A cycle in a graph is Hamiltonian if it includes every vertex.
• Hamiltonian cycles are used in planning routes which must visit every location in some set, without visiting any location twice, and returning to the starting point.
• The problem of finding the Hamiltonian cycle of minimum total cost is known as the Travelling Salesman Problem (TSP).

11.9 Connectivity

• Two vertices $v$ and $w$ in a graph $G$ are connected if there is a path from $v$ to $w$ in $G$.
• A graph $G$ is connected if, for every pair of vertices $v$ and $w$, there is a path from $v$ to $w$ in $G$.
• A component of $G$ is a maximal connected subgraph of $G$.
• Connectivity defines an equivalence relation $R$ on the vertices $V$ of a graph $G = (V, E)$:
  • For all $v, w ∈ V, vRw$ if and only if there is a walk from $v$ to $w$ in $G$.
  • This relation is reflexive, symmetric, and transitive.
• The equivalence classes of $R$ partition $V$ and are the vertex sets of the components of $G$.

11.10 Bipartite Graphs

• A graph $G = (V, E)$ is bipartite if its vertex set $V$ can be written as a disjoint union $V = A ⊔ B$ such that every edge has one endpoint in $A$ and the other in $B$.
• A complete bipartite graph is a bipartite graph in which every pair of vertices on different sides is adjacent.
• If the two sides have $p$ and $q$ vertices then we denote the complete bipartite graph by $K_{p,q}$.

Theorem 61

• A graph is bipartite if and only if it has a 2-coloring (a function that assigns one of two colors to each vertex such that adjacent vertices have different colors).
  • (⟹) Suppose $G$ is bipartite, and let $A$ and $B$ be the two sides, so all edges have one endpoint in $A$ and the other in $B$. Define a function which colours all vertices in $A$ Black and all vertices in $B$ White. Then every edge has one endpoint coloured Black (because it is in $A$) and the other endpoint coloured White (because it is in $B$). Therefore adjacent vertices always get different colors. Therefore this function is a 2-colouring of $G$.
  • (⟸) Suppose $G = (V,E)$ has a 2-colouring $f∶V→{Black,White}$. Let $A=f^{−1}(Black)$ be the set of all vertices coloured Black, and let $B=f^{−1}(White)$ be the set of all vertices coloured White. Every vertex of $V$ belongs to one of these two sets, since every vertex is mapped to one of those two colours. Furthermore, no vertex can belong to both sets, because $f$ is a function and therefore cannot assign two different values to any element of its domain. Therefore $V = A⊔B$. Also, since adjacent vertices get different colours under $f$, adjacent vertices must belong to different sets ($A$ or $B$); they cannot both belong to the same set, for then they would be given the same colour by $f$.

Theorem 62

• A graph is bipartite if and only if it has no odd closed walk.
  • (⟹) If $G$ is bipartite, then every walk must alternate between vertices in $A$ and vertices in $B$. So, it goes from a vertex in $A$, to a vertex in $B$, to one in $A$, to one in $B$, and so on, possibly with repetition of vertices and edges. At every stage, if we are at a vertex in $A$, then two steps later we are back in $A$. This alternation ensures that a closed walk has even length. Therefore $G$ has no odd closed walk.
  • (⟸) If $G$ has no odd closed walk, then for each component of $G$: choose one vertex in the component as the “ground vertex” of that component. Call it $g$. Colour $g$ Black. Then colour every other vertex $v$ of the component as follows: Colour of $v$ = Black, if the distance from $g$ to $v$ is even; White, if the distance from $g$ to $v$ is odd. Assume, by way of contradiction, that our assignment of colours is not a 2-colouring of $G$. Then there must be two adjacent vertices that get the same colour. Let $X$ be this colour, which could be Black or White. Let $v$ and $w$ be these two adjacent vertices, each with colour $X$. Since they are adjacent, they must belong to the same component of $G$. Let $g$ be the ground vertex for that component. Key observation: the distances from $g$ to $v$, and from $g$ to $w$, have the same parity. Since these two distances have the same parity, their sum is even. Let $P$ be a shortest path in $G$ from $g$ to $v$, and let $Q$ be a shortest path in $G$ from $g$ to $w$. The lengths of these two paths have the same parity, as explained in the previous paragraph. So length of $P$ + length of $Q$ is even. Now consider the walk formed by starting at $v$, going along $P$ to $v$, then stepping along edge ${v,w}$ to $w$, then going along $Q$ from $w$ back to $g$, finishing up at $g$. This is a closed walk, since it finishes where it starts. Its length is length of $P$ + length of $Q$ + 1, where we now have an extra +1 because of the edge ${v,w}$. We have already seen that the sum of the lengths of $P$ and $Q$ is even. It follows that the length of this closed walk is odd. So we have constructed an odd closed walk in $G$.

Corollary 63

• A graph is bipartite if and only if it has no odd cycle.

11.11 Euler Tours

• An Euler tour is a closed trail that uses every edge exactly once and finishes at its starting vertex.

Theorem 64 (Euler, 1736)

• A connected graph $G$ has an Euler tour if and only if every vertex has even degree.
  • (⟹) Let $G$ be a connected graph with an Euler tour. An Euler tour is a trail, and when a trail passes through a vertex, it uses two of the edges incident with that vertex: one on the way in, and one on the way out. An Euler tour uses each edge of the graph exactly once. It follows that it must revisit each vertex as many times as necessary in order to use each of its incident edges exactly once, and it uses two edges for each visit, so the number of incident edges at the vertex must be a multiple of 2. Therefore each vertex degree is even.
  • (⟸) Let $G$ be a connected graph in which every vertex has even degree. We give an algorithm for constructing an Euler tour for $G$. Initialisation: Choose any vertex $v$ of $G$. Let $T$ be the trivial closed trail consisting just of the vertex $v$, with no edges.While there is at least one edge we have not yet used in $T$: Find a vertex in $T$ that has at least one edge that we have not yet used in $T$. Call it $v$.Walk along an edge incident at $v$ Starting anywhere on $T$, we follow $T$ until we first reach $v$. Then we follow $U$ all the way until we return to $v$ for the last time, having stepped along all edges of $U$. Then we resume following $T$, and we follow it all the rest of the way until we return to our starting vertex for the last time, having used every vertex of $T$.
• A graph is Eulerian if it contains an Euler tour.

Theorem 65

• For any $k ∈ ℕ$, the edges of a graph can be partitioned into $k$ trails if and only if the graph has at most $2k$ vertices of odd degree.
• The open trails in such a partition start and end at odd-degree vertices.

11.12 Exercises

• Exercise questions about:
  • Predicate logic expressions for graph properties.
  • Bit representation of graphs using different methods.
  • Rewriting the proof of Theorem 56.
  • Calculating edges and average degree of a caffeine molecule graph.
  • Proving shortest walks are paths.
  • Graphs with cycles and triangle inequality.
  • 2-colorings of bipartite graphs.
  • Trails and Euler tours in multigraphs.
  • Hamiltonian and Eulerian cycles in platonic solids.
  • Hamiltonian cycle construction in bit string graphs.
  • Extending Theorem 64 to multigraphs.