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…

Definition of graph theory