page1
Chapter 10 Formulas / Theorems sheet
Type
Edges
Multiple edges allowed?
Loops allowed?
Simple graph
undirected
No
No
Multigraph
undirected
Yes
No
Pseudograph
undirected
Yes
Yes
Simple directed graph
directed
No
No
Directed multigraph
directed
Yes
Yes
Mixed graph
both types
Yes
Yes
[Theorem 1] The Handshaking Theorem
Let G = (V,E) be an undirected graph with m edges.
Then
[Theorem 2] An undirected graph has an even number of vertices of odd degree.
[Theorem 3] Let G = (V,E) be a directed graph. Then
[Def] a simple graph is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (i.e. no same-set vertices connections). We call the pair (V1, V2) a bipartition of V.
[Theorem 4] a simple graph is bipartite if and only if (iff) it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertics have the same color.
[Theorem] Hall's marriage theorem
The bipartite graph G = (V,E) with bipartition (V1,V2) has a complete matching from V1 to V2 if and only if (iff) |N(A)|  |A| for all subsets A of V1.
[Theorem] There is a simple path between every pair of distinct vertices of a connected undirected graph.
[Def] An Euler circuit in a graph G is a simple circuit containing every edge of G.
[Def] An Euler path in G is a simple path containing every edge of G
[Theorem] A connected multigraph with at least two vertices has an Euler circuit iff each of its vertices has even degree.
[Theorem] A connected multigraph has an Euler path but not an Euler circuit iff it has exactly two vertices of odd degree.
[Theorem] A directed graph has an Euler circuit iff all vertices with nonzero degree belong to a single strongly connected component and in-degree and out-degree of every vertex is same.
[Theorem] A directed graph has an Euler path iff
[Def] A Hamilton circuit in a graph G is a simple circuit that passes through every vertex in G exactly once.
[Def] A Hamilton path in a graph G is a simple path that passes through every vertex in G exactly once.
Properties:
at most one vertex has (out-degree) − (in-degree) = 1,
at most one vertex has (in-degree) − (out-degree) = 1,
every other vertex has equal in-degree and out-degree, and
all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.
A graph with a vertex of degree 1 cannot have a Hamilton circuit (each vertex is incident with two edges)
If a vertex in the graph has degree 2, then both edges that are incident with this vertex must be part of the Hamilton circuit.
When a Hamilton circuit is being constructed and it passed through a vertex, then all remaining edges incident with this vertex, other than the two used in the circuit, can be removed from consideration.
A Hamilton circuit cannot contain a smaller circuit within it.