page1
Graphs 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 graph with all the vertices of the same degree is called a regular graph.
In a d-regular graph, all the vertices have degree d.
[Def]: A graph H = (VH, EH) is a subgraph of a graph G = (VG, EG) if VH  VG and EH ⊆ EG.
Note: graph G is a subgraph of itself
Special Simple Graphs:
- complete graphs ( Kn, for n  Z+ )
- cycles ( Cn, for n  Z+ and n  3)
- wheels ( Wn, for n  Z+ and n  3)
- n-cubes ( Qn, for n  Z+ )
[Theorem] There is a trail between every pair of distinct vertices of a connected undirected graph.
[Def] An Euler circuit in a graph G is a circuit containing every edge of G.
[Def] An Euler trail in G is a trail 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 trail but not an Euler circuit iff it has exactly two vertices of odd degree.
[Def] A Hamilton cycle in a graph G is a cycle that passes through every vertex in G.
[Def] A Hamilton path in a graph G is a path that passes through every vertex in G.
Properties:
[Theorem] Dirac's Theorem
If G is a simple graph with n vertices with n  3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton cycle.
[Theorem] Ore's Theorem
If G is a simple graph with n vertices with n  3 such that deg(u)+deg(v)  n for every pair of non-adjacent vertices u and v in G, then G has a Hamilton cycle.
A graph with a vertex of degree 1 cannot have a Hamilton cycle (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 cycle.
When a Hamilton cycle is being constructed and it passed through a vertex, then all remaining edges incident with this vertex, other than the two used in the cycle, can be removed from consideration.
A Hamilton cycle cannot contain a smaller cycle within it.
K1
Q1, K2
K3, C3
K4
K5
C5
C6
Q2, C4
W3
W4
W5
W6
Q3