ECM 1415 Graph Theory Flashcards
Simple Graph
Each edge connects two different vertices and no two edges connect the same pair of vertices.
Multigraphs
Have multiple edges connecting the same two vertices.
Pseudograph
May include loops, as well as multiple edges connecting the same pair of vertices
Directed graph
Each edge is associated with an ordered pair of vertices (u, v)
Such an edge is said to start at u and end at v
u is the initial vertex of this edge and is adjacent to v and v is the terminal (end) vertex of this edge and is adjacent from u
Simple Directed Graph
No loops or multiple edges
Directed multigraph
Multiple directed edges
Mixed Graph
Can have directed and undirected, with multiple edges and loops
Neighborhood
The set of all neighbours of a vertex
Degree
The number of incident edges a vertex has
- A loop at a vertex contributes 2 to the degree of that vertex
Handshaking Theorem
If G = (V, E) is an undirected graph with m edges then,
2m = Total number of degrees of freedom
Each edge contributes 2 to the degree count of all vertices because an edge is incident with exactly 2 (possibly equal) vertices
This means that the sum of the degrees of the vertices is twice the number of edges
In-degrees and Out-degrees
In-degree: The number of edges which terminate at v
Out-degree: The number of edges with v as their initial vertex
Let G = (V, E) be a graph with directed edges. Then,
|E| = Number of Out-degrees = Number of In-degrees
Because each edge has an initial vertex and a terminal vertex, the sum of the in-degrees and the sum of the out-degrees of all vertices in a graph with directed edges are the same
Both of these sums are the number of edges in the graph
Complete Graph on n vertices
Kn. The simple graph that contains exactly one edge between each pair of distinct vertices
No graph Kn is bipartite for n >= 2
Cycle Graphs, Cn
The edges loop. Visually, there is a hole in the graph.
The number of vertices must be even for the graph to be bipartite
Wheel graphs, Wn
Like Cn, But there is a vertex in the middle, with all other surrounding vertices connecting to it
The number of vertices must be odd for the graph to be bipartite
n-Cube Graphs, Qn
A graph with 2^n vertices representing all bit strings of length n, where there is an edge between 2 vertices that differ in exactly one bit position
No Qn can be bipartite
What is a path
A sequence of n edges in a graph
What is a circuit
A path that begins and ends on the same vertex
When is a path/circuit simple?
If it doesn’t contain the same edge more than once
What is a graph isomorphism?
If one graph is isomorphic to another (retains the same base structure)
How to find a graph isomorphism between two graphs
Follow paths that go through all vertices so that the corresponding vertices in the two graphs have the same degree
What is a connected graph?
An undirected graph is called connected if there is a path between every pair of vertices
An undirected graph that is not connected is called disconnected
We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph
The strength of connection in directed graphs (strong and weak)
Strongly connected: There is a path from a to b and a path from b to a whenever a and b are vertices in the graph
Weakly connected: There is a path between every two vertices in the underlying undirected graph
Connected component
A connected subgraph
Euler Circuit
A simple circuit containing every edge of the graph
Euler Path
A simple path containing every edge of G
Hamiltonian path/circuit
A simple path/circuit that passes through every vertex exactly once
Dirac’s Theorem
If G is a simple graph with n >= 3 vertices such that the degree of every vertex in G is >= (n/2), then G has a Hamilton circuit
Ore’s Theorem
If G is a simple graph with n >= 3 vertices such that deg(u) + deg(v) >= n for every pair of nonadjacent vertices, then G has a Hamilton circuit
Planar Graph
The graph can be drawn without any edges crossing
Euler’s Formula
r = e - v + 2
Corollaries (Euler’s Formula)
If G is a connected planar simple graph with e edges and v vertices, where v >= 3, then e <= 3v - 6
If a connected planar simple graph has e edges and v vertices with v >= 3 and no circuits of length three, then e <= 2v - 4
How to calculate the number of unique hamilton paths/circuits on a complete graph?
(n-1)! / 2
Euler’s Theorem
If a graph has more than two vertices of odd degree, then it cannot have an Euler path. If a graph is connected and has exactly two vertices of odd degree, then it has at least one Euler path (usually more). Any such path must start at one of the odd-degree vertices and end at the other one.
