All You Need to Know about Graph Theory

1. A graph G consists of a set V of nodes (or vertices) and a (multi)set E of edges connecting pairs of nodes. If v and w are vertices, the edge connecting them is written as (v,w). Note that we allow (v,v) as an edge. We also allow several copies of (v,w) in the edge set (representing multiple edges between two vertices). However, neither of these possibilities is allowed in a simple graph.,
2. A path in a graph is a sequence of edges that are connected one to the next.
3. A cycle in a graph is a closed path in the graph.
4. A graph G is connected if for any two distinct vertices v and w of the graph, there is a path joining v and w.
5. A Hamiltonian path in a graph is a path that visits each vertex of the graph exactly once.
6. A Eulerian path in a graph is a path that visits each edge of the graph exactly once.
7. A graph G is l-colored if its edge set E is partitioned into l subsets and a distinct color is associated with each subset.
8. A path (or cycle) P in an l-colored graph G is called alternating if adjacent edges in P are of different colors. Note that alternating cycles in a 2-colored (bicolored) graph must contain an even number of edges.
9. We can define two operations, called collectively order transformations on alternating paths in bicolored graphs as follows. Assume that P is an alternating path that passes through the vertex v twice, so that P = P₁ v P₂ v P₃. The order reflection of P is the path P₁ v P₂^- v P₃. It is an alternating path if and only if P₂ has odd length.

   To define an order exchange on an alternating path P, assume that P passes through two vertices v and w twice, so that P = P₁ v P₂ w P₃ v P₄ w P₅. The order exchange of P is the path P₁ v P₄ w P₃ v P₂ w P₅.

10. A directed graph is a graph in which each edge has a direction, usually represented as an arrow from a vertex v to a vertex w.
11. A complete graph is a graph in which every pair of distinct vertices is connected by an edge.
12. An Eulerian graph is a (directed) graph that has a cycle, called an Eulerian cycle, that contains every (directed) edge exactly once.
13. The degree d(v) of a vertex v of a graph is the number of edges incident on the vertex.
14. The color degree d_c(v) for color c of a vertex v of an l-colored graph is the number of edges of color c incident on the vertex.
15. A vertex v of an l-colored graph is balanced if the maximum of its color degrees is less than or equal to its degree/2. Note that in a bicolored graph, d₁(v) + d₂(v) = d(v) so that a balanced vertex has the same number of edges of each of the two colors incident on it.
16. An l-colored graph is balanced if every vertex is balanced.
17. Theorem (Kotzig):  Let G be a connected l-colored graph whose vertices all have even degree. Then there is an alternating Eulerian cycle in G if and only if G is balanced.
18. Corollary:   Let G be a connected bicolored graph. Then there is an alternating Eulerian cycle in G if and only if for every vertex v of G, we have d₁(v) = d₂(v).
19. Theorem: (Pevzner, p.28)   Let G be a connected, balanced, bicolored graph. The alternating Eulerian cycle in G (known to exist from the Corollary above) is unique up to order transformation.
20. The indegree of a vertex of a directed graph is the number of edges leading into the vertex.
21. The outdegree of a vertex of a directed graph is the number of edges leading out of the vertex.
22. A vertex v of a directed graph is balanced if   indegree(v) = outdegree(v).
23. A vertex v of a directed graph is semibalanced if   |  indegree(v) - outdegree(v)  | = 1.
24. Theorem:   A connected, directed graph is Eulerian if and only if each vertex is balanced.
25. Theorem:   A connected, directed graph has an Eulerian path if and only if the graph contains at most two semibalanced vertices and all other vertices are balanced.