\( \newcommand{\defint}[4]{\int_{#1}^{#2}\,#3\,d#4} \)
Graph Theory
Robert Beezer
beezer@pugetsound.edu
Department of Mathematics and Computer Science
University of Puget Sound
June 28, 2013
Chapter 1
Connectivity

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

1.1 Walks, Paths, Trails

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

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

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

Chapter 2
Algebraic Graph Theory

This is one of my favorite topics.

2.1 Adjacency Matrices

Might as well begin here.

2.1.1 The Basics

We should first make a definition.

Definition 1.1 Given a graph \(G\), we define the adjacency matrix \(A(G)\) as the \(0\)-\(1\) matrix given by: \[A(G)=\begin{cases} 0 &\text{ if }v_i\text{ and }v_j\text{ are adjacent}\\ 1 &\text{otherwise} \end{cases}\]

When no confusion will result, we will denote this matrix simply as \(A\).

Sample notation (in a master list eventually): \(A(G)\)

2.2 Eigenvalues

This is where the fun would start.