Basic Definitions

Every graph has a bipartite subgraph containing at least half of the edges of the graph.

A path in a graph is a sequence $v_{1} e_{1} v_{2} e_{2} \ldots e_{n-1} v_{n}$ in which, for every $i$, the edge $e_{i}$ joins the vertices $v_{i}$ and $v_{i+1}$. The number $n-1$ is called the length of the path. (The edges $e_{1}, e_{2}, \ldots , e_{n-1}$ need not be pairwise distinct.)

A cycle in a graph is a sequence $v_{1} e_{1} v_{2} e_{2} \ldots e_{n-1} v_{n} e_{n}$ in which, for every $i < n$, the edge $e_{i}$ joins the vertices $v_{i}$ and $v_{i+1}$, and the edge $e_{n}$ joins the vertices $v_{n}$ and $v_{1}$. Cycles are considered the same if they differ by a cyclic shift of the sequence. The number $n$ is called the length of the cycle.

A cycle is called non-self-intersecting if its vertices $v_{1}, v_{2}, \ldots , v_{n}$ are pairwise distinct and its edges $e_{1}, e_{2}, \ldots , e_{n}$ are pairwise distinct. The standard term (less convenient for beginners) is a simple cycle.

If the degree of each of the $n$ vertices of a graph is greater than $\frac{n}{2}-1$, then the graph is connected.

Let a directed graph $G$ be given, with a weight $f(u)$ written on each edge $u$. (This weight can be understood as the work that must be expended in order to traverse the edge from its start to its end.) A function $p: V(G) \to \mathbb {R}$ (a potential'') such that $f(x,y) = p(x) - p(y)$ for every edge $u = (x,y)$ exists if and only if the sum of the weights of the edges of every cycle equals zero (when an edge is traversed along the cycle in the direction opposite to its orientation, its weight enters the sum with a minus'' sign).