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