Basic Definitions

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

Basic parts of a graph.

Instead of E(G)E \parens{G}, a directed graph (or digraph) has a set D(G)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?

Directed graph. Undirected multigraph. Weighted undirected graph.

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?

A tree.

A list.

(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 KnK_n. Make diagrams for them. (Epp, Page 633)

TODO: Define complete bipartite graphs Km,nK_{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 HH is a connected component of its supergraph GG iff HH is connected, and no connected subgraph of GG is a supergraph of HH that also contains vertices and edges not in HH. TODO: Can we simplify this definition? Also, we should draw diagrams for this.

The degree of a vertex (denoted deg(v)\mathrm{deg}\parens{v} for the degree of vertex vv) 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.