# Graphs

# THIS PAGE IS A VERY EARLY WORK-IN-PROGRESS.

## Basic Definitions

A graph $G$ consists of two finite sets: a nonempty set $V \parens{G}$ of *vertices*, and a set $E \parens{G}$ of *edges*, where each edge is associated with a set consisting of either one or two vertices called its *endpoints*.

Instead of $E \parens{G}$, a *directed graph* (or *digraph*) has a set $D \parens{G}$ of *directed edges*. A *mixed graph* can contain both directed and undirected edges.

A *weighted graph* has valued edges. A *multigraph* may have parallel edges. A *simple graph* has no loops or parallel edges.

TODO: Below in order are: Directed graph, undirected multigraph, and weighted undirected graph. Is there a way to annotate captions?

A *list* is a graph with only one *path*. A *tree* is a graph with exactly one path between each pair of vertices.

TODO: Below in order are: A tree and a list. Is there a way to annotate captions?

*(Many more graph variations exist, but an exhaustive list is beyond the scope of a quick reviewer.)*

A *walk* is an alternating sequence of __adjacent__ vertices and edges. A walk with only one vertex (and no edges) is a *trivial walk*. A *closed* walk starts and ends on the same vertex.

A *trail* is a walk with no repeated edges. A *circuit* is a closed trail with at least one edge.

A *path* is a walk with no repeated edges or vertices. A *simple circuit* is a closed path except it starts and ends on the same vertex, and has at least one edge.

TODO: Diagram for path? Also, we should rework these walk/trail/path and related definitions.

TODO: Define *complete graphs* $K_n$. Make diagrams for them. (Epp, Page 633)

TODO: Define *complete bipartite graphs* $K_{m,n}$. Make diagrams for them. (Epp, Page 633)

TODO: Define *subgraph*. (Epp, Page 634)

Two vertices are *connected* iff there is a walk between them. A graph is *connected* iff there is a walk between every pair of its vertices.

A graph $H$ is a *connected component* of its supergraph $G$ iff $H$ is connected, and no connected subgraph of $G$ is a supergraph of $H$ that also contains vertices and edges not in $H$. TODO: Can we simplify this definition? Also, we should draw diagrams for this.

The *degree* of a vertex (denoted $\mathrm{deg}\parens{v}$ for the degree of vertex $v$) is the number of edges incident on it, with loops counted twice. The *total degree* of a graph is the sum of the degrees of all vertices in the graph.

## Graph Representation

TODO: this## More Theoretical Results

TODO: What theoretical results are useful to include here? Should we create a separate section for stuff towards the end of the chapter that aren’t quite as useful for typical algorithms problems?

TODO: Include *degree sum formula*: The sum of all degrees of a graph is twice the number of its edges. Corollary: the total degree of the graph is also be even. (Epp, Page 636)

TODO: Include *handshake lemma* (lemma of degree sum formula): There is an even number of vertices of odd degree.

TODO: Consider including connectedness lemmas. (Epp, Page 647)

TODO: Königsberg bridge problem: If a graph has an Euler circuit, every vertex has positive even degree. If a connected graph has positive even degree, it has an Euler circuit. If a graph has odd degree, then it has no Euler circuit. A connected graph has an Euler circuit iff every vertex has positive degree. (Epp, Page 652)

TODO: The corollary on Epp Page 653: There is an Euler path iff the graph is connected, the start and end vertices have odd degree, and all other vertices have even degrees.

## More Definitions

TODO: This is actually a temporary section and will probably not be in the final version. I’m just using it to write down some interesting definitions that might be useful later.

TODO: Consider adding *Euler circuit*: A circuit that contains every vertex and edge of a graph. (That is, every edge is used exactly once, but vertices can be used multiple times.)

TODO: Consider adding *Euler trail*: A trail that passes through every edge of a graph once, and every vertex at least once.

## References

*Discrete Mathematics with Applications*($\Nth{4}{th}$ edition) by Susanna S. Epp, Chapter 10- A major resource I used to learn about graphs and write this section out. Highly recommended to go through it yourself if you’re still learning.
- I like the first sentence of the definition on page 626, so I copied it verbatim for the first sentence of Basic Definitions.

__Wikipedia__