Combinatorics: The Fine Art of Counting
Week 9 Lecture Notes – Graph Theory
For completeness I have included the definitions from last week’s lecture which we will be using
in today’s lecture along with statements of the theorems we proved.
Definitions
Graph: A graph G = (V, E) consists of an arbitrary set of objects V called vertices and a set E
which contains unordered pairs of distinct elements of V called edges.
Adjacent: Two vertices in a graph are adjacent if there is an edge containing both of them. Two
edges are adjacent if they contain a common vertex. Adjacent vertices are called neighbors.
Degree: For any vertex v in a graph, the degree of the vertex is equal to the number of edges
which contain the vertex. The degree of v is denoted by d(v).
Regular Graph: A graph in which every vertex has the same degree is called a regular graph. If
all vertices have degree k, the graph is said to be k-regular.
Complete Graph: The complete graph on n vertices Kn consists of the vertex set V =
{v1,v2,…,vn} and the edge set E containing all pairs (vi,vj) of vertices in V.
Isomorphic: Two graphs are isomorphic if there exists a one-to-one correspondence between
their vertex sets (i.e. a re-labeling) which induces a one-to-one correspondence between their
edge sets. More formally, if L is a re-labeling which maps the vertices of G to the vertices of H,
then the edge set of H is precisely the set of edges (L(v),L(w)) where (v,w) is an edge in G.
Sub-graph: A graph G1 = (V1, E1) is a sub-graph of G2 = (V2, E2) whenever V1 ⊆ V2 and
E1 ⊆ E2.
Path: A path of length n is the graph Pn on n+1 vertices {v0, v1, v2, …, vn} with n edges (v0,v1),
(v1,v2), …, (vn-1,vn).
Cycle: A cycle of length n is the graph Cn on n vertices {v0, v2, …, vn-1} with n edges (v0,v1),
(v1,v2), …, (vn-1,v0).
We say that a given graph contains a path (or cycle) of length n if it contains a sub-graph which
is isomorphic to Pn (or Cn).
Connected: A graph that contains a path...