Graph Theory

\( \newcommand{\defint}[4]{\int_{#1}^{#2}\,#3\,d#4} \)

Chapter 1
Connectivity

1.1 Introduction

Cross-file mathjax reference: \ref{blatzo}

We might rightly begin an exploration of graph theory with topics grouped together with a common theme of connectivity.

1.2 Walks, Paths, Trails

There is often considerable confusion about these terms. Consider the following definition.

Definition 1 A walk in a graph is a sequence of vertices such that consecutive vertices in the sequence are adjacent in the graph.

Theorem 1 Suppose that \(A\) is the adjacency matrix of a graph, then the number of walks in the graph of length \(k\), between vertices \(v_i\) and \(v_j\) is the \((i,j)\) entry of \(A^k\).

Proof Induction on \(k\), with the definition of matrix multiplication.

So this definition does not preclude visiting a vertex more than once, nor going back-and-forth along a single edge.