Introduction to Graph Theory

Introduction
• The three sections we are covering tonight have in
common that they mostly contain definitions. Graph
theory suffers from a large number of definitions that
mathematicians use inconsistently. For instance, what
some mathematicians call a graph, others call a simple
graph. What some mathematicians call a multigraph,
other just call a graph. Some mathematicians call a
graph labeled if the vertices are labeled, while others
mean that the edges are labeled.

2
 Introduction
• Why are the definitions so confused in graph theory? I
suspect it is simply a matter of convenience. People who
want to write about simple graphs make their lives easier
by just calling them graphs. People who want to write
about multigraphs call them graphs. The caveat in all of
this is clear: when you start to read a new book on graph
theory read the definitions carefully to make sure of the
ground rules.

3
 Graphs: Basic Definitions
• A graph, G, comprises a set V of vertices and a set E of
edges. The vertex set can be anything, but is most
commonly a collection of letters or numbers. The set of
edges is a set of doubleton subsets of V. That is
E⊆{{a,b}:a,b∈V and a≠b}. We denote the graph by
G(V,E).
• If G(V,E) is a graph and {a,b}∈E, then we say vertices a
and b are adjacent and the edge {a,b} joins them or
connects them or is incident on them. We call a and b the
endpoints of the edge. Two edges that share one vertex,
such as {a,b} and {b,c} with a≠c, are adjacent to each
other.

4
 Graphs: Representation
• Normally we think of a graph as a drawing. A little
reflection shows that the definition above is a
formalization of this intuition about graphs. We think of
a graph comprising dots (vertices) connected by line
segments or curves (edges). We give every dot a label
and form the vertex set V out of the labels. If there is a
curve connecting dots a and b, we include the edge {a,b}
in E.

5
 Graphs: Examples
• Let V={a,b,c,d} and E={{a,b},{a,c},{b,c},{c,d}}
b
a

d
c

6
 Graphs: Examples
• Let V={a,b,c,d} and E={{a,b},{a,c},{a,d},{b,c},{b,d},
{c,d}}. This is called the complete graph on four
vertices, denoted K4.

a b

c d

7
 Graphs: Examples
• Let V={a,b,c,d} and E=∅.

a b

c d

8
 Graphs: Variant Definitions
• Our definition of graph does not allow an edge to join a
vertex to itself. Such an edge is called a loop, and some
definitions of graph allow them. Our text refers to such a
structure as a graph with loops (clever, huh?), which is a
straightforward name but not common as far as I know.
Some definitions of graph allow for multiple edges
between the same two vertices. Our book calls this
structure a multigraph (which is a common and helpful
usage in that it makes E a multiset rather than a set). Our
book calls a multigraph with loops a pseudograph. I
think this terminology may be standard, but I am not a
graph theorist.
9
 Graphs: Applications
• On p. 229 the book mentions the application of graphs to
printed circuit and microchip design. Graphs seem an
intuitively natural way to model many situations in the
Creation (connections of wires/leads,
logistics/transportation problems, pipelines between
points with known capacities, family trees,
organizational charts, among many more). This suggests
why graph theory has grown so dramatically in the past
century.

10
 Graphs: More Definitions
• The degree of a vertex is the number of edges incident
on the vertex. That is, if G(V,E) is a graph and a∈V, then
degree(a)=|{x:{a,x}∈E}|. Put another way, the degree of
a vertex is the number of vertices adjacent to it. If a
vertex has no adjacent vertices (degree 0), then it is
isolated.

11
 Graphs: Theorems on Degree
• The sum of the degrees of the vertices of a graph is even.
Proof: Each edge joins two vertices. Thus adding up the
degrees of the vertices is equivalent to counting all the
edges twice. Therefore the sum of the degrees is even. In
fact it is twice the number of edges.
• Every graph has an even number of vertices of odd
degree. Proof: Otherwise the sum of the degrees would
be odd.

12
 Graphs: Subgraphs
• A graph G′(V′,E′) is a subgraph of the graph G(V,E) if V
′⊆V and E′⊆E. Note that this does require G′(V′,E′) to
be a graph, so one cannot form a subgraph of arbitrary
subsets of V and E. The second graph below is a subset
of the first.
b a b
a

c
c d

13
 Graphs: Paths
• The notion of a path in a graph is intuitively clear but a little hard to
pin down formally. Suppose G(V,E) is a graph with vertices v 0,v1,
…,vk (not necessarily distinct) and edges e1,e2,…,ek (not necessarily
distinct) in which edge ei={vi-1,vi} for i=1,…,k. Then the alternating
sequence of vertices and edges v0e1v1e2v2…ekvk is a path from v0 to vk
of length k (note that the length is the number of edges, not vertices).
Unless we work with multigraphs the listing of the edges is redundant,
so we may speak more simply of the path as v0v1v2…vk. This
definition allows for incredibly knotty, repetitious paths. If we want to
rule out that possibility, we can speak of simple paths, which are paths
in which no vertices (and thus no edges) are repeated.
14
 Graphs: An Example of a Path
• Example: In the following diagram the red edges show a
simple path of length three from a to e. The path is acde.
Of course this could also be the non-simple path
acdcacacdede of length 11.
a

c
b

d e

15
 Graphs: Connectedness
• Intuitively a graph is connected if it has no parts that are isolated from each
other, if you can get from each part to every other part. Formally we say a
graph is connected if there exists a path between every pair of distinct vertices.
Clearly this is equivalent to saying there is a simple path between every pair of
distinct vertices. The graph just given is connected, but the following one is not
since you cannot, for instance, get from a to d.

b c

d e

16
 Graphs: Components
• A component is a maximal connected subgraph. For
instance the previous graph has two components, one
consisting of a,b,c and their edges, the other consisting
of d,e and their edge. Formally a subgraph G′ of graph G
is a component if G′ is connected (and nonempty) and
every other connected subgraph of G that contains G′
equals G′ (this second condition is what we mean by
maximal in this context).

17
 Graphs: Components
• A cycle is a nontrivial (length>0) path whose initial and
terminal vertices are the same and which has no repeated
edges. If no vertex is repeated except that the initial
vertex equals the terminal one, then the cycle is simple.
An n-cycle is a simple cycle of length n. In the following
graph, the simple cycle acbda (in red) is a 4‑cycle while
adecdba is a non-simple cycle (no edges repeat, but the
vertex d does) a

c
b

d e

18
 Graphs: Components
• A graph in which an edge joins every pair of distinct
vertices is a complete graph. We denote by Kn the
complete graph on n vertices. A bipartite (two-part)
graph G(V,E) is one in which we can partition V into two
subsets A and B such that every edge in E joins a vertex
in A to a vertex in B. If an edge joins every vertex in A to
every vertex in B, then G is a complete bipartite graph.
In that case if |A|=m and |B|=n, then we denote the
complete bipartite graph by Km,n. The book shows
examples of these graphs in the figures at the bottom of
page 231.
19
 Graphs: Components
• Bipartite graphs arise naturally in many contexts. For
instance imagine that we make a list of students on the
left edge of a page, make a list of courses on the right
edge of a page, and then draw lines between students and
the courses they have taken. The result is a bipartite
graph. Similarly if we draw the graph of a relation from
a set A to a set B, then the result is a bipartite graph.

20
 Directed Graphs (Digraphs)
• A directed graph (digraph, for short) G consists of a set
V of vertices and a set E of directed edges. A directed
edge is an ordered pair of elements of V. Put another
way, the pair G(V,E) with E⊆V×V is a digraph.
• Differences from graphs: Digraphs allow for loops of the
form (a,a), It is also possible to have two edges (a,b) and
(b,a) between vertices a and b. We take the ordering of
the pairs in E to give each edge a direction: namely the
edge (a,b) goes from a to b. We call a the initial vertex
and b the terminal vertex of the edge. When we draw the
digraph, we draw the edge (a,b) as an arrow from a to b.

21
 Digraphs: Example
• Example: Let V={a,b,c,d} and E={(a,b),(a,c),(b,a),(c,c),
(d,c)}

b
a

d
c

22
 Trees: Definition & Applications
• A tree is a connected graph with no cycles. A forest is a graph
whose components are trees. An example appears below. Trees
come up in many contexts: tournament brackets, family trees,
organizational charts, and decision trees, being a few examples.

23
 Directed Trees
• A directed tree is a digraph whose underlying graph is a tree and
which has no loops and no pairs of vertices joined in both
directions. These last two conditions mean that if we interpret a
directed tree as a relation, it is irreflexive and asymmetric. Here is
an example.

24
 Trees: Theorem on Leaves
• Theorem: A tree T(V,E) with finite vertex set and at least one edge
has at least two leaves (a leaf is a vertex with degree one). Proof:
Fix a vertex a that is the endpoint of some edge. Move from a to
the adjacent vertex along the edge. If that vertex has no adjacent
vertices then it has degree one, so stop. If not, move along another
edge to another vertex. Continue building a path in this fashion
until you reach a vertex with no adjacent vertices besides the one
you just came from. This is sure to happen because V is finite and
you never use the same vertex twice in the path (since T is a tree).
This produces one leaf. Now return to a. If it is a leaf, then you are
done. If not, move along a different edge than the one at the first
step above. Continue extending the path in that direction until you
reach a leaf (which is sure to happen by the argument above).

25
 Trees: Leaves & Internal Vertices
• In the following tree the red vertices are leaves. We now know
every finite tree with an edge has a least two leaves. The other
vertices are internal vertices.

26
 Trees: Equivalent Condition on Paths
• Theorem : Given vertices a and b in a tree T(V,E), there is a
unique simple path from a to b. Proof: Trees are connected, so
there is a simple path from a to b. The book gives a nice example
of using the contrapositive to prove the rest of the theorem.
• Theorem : Given a graph G(V,E) such that every pair of vertices is
joined by a unique simple path, then G is a tree. Proof: Since a
simple path joins every pair of points, the graph is connected.
Now suppose G has a cycle abc…a. Then ba and bc…a are
distinct simple paths from b to a. This contradicts uniqueness of
simple paths, so G cannot possess such a cycle. This makes G a
tree.

27
 Rooted Trees
• Sometimes it is useful to distinguish one vertex of a tree and call it
the root of the tree. For instance we might, for whatever reasons,
take the tree above and declare the red vertex to be its root. In that
case we often redraw the tree to let it all “hang down” from the
root (or invert this picture so that it all “grows up” from the root,
which suits the metaphor better)

28
 Rooted Directed Trees
• It is sometimes useful to turn a rooted tree into a rooted directed
tree T′ by directing every edge away from the root.

29
 Rooted Trees: Terminology
• Rooted trees and their derived rooted directed trees have
some useful terminology, much of which is suggested by
family trees. The level of a vertex is the length of the
path from it to the root. The height of the tree is the
length of the longest path from a leaf to the root. If there
is a directed edge in T′ from a to b, then a is the parent of
b and b is a child of a. If there are directed edges in T′
from a to b and c, then b and c are siblings. If there is a
directed path from a to b, then a is an ancestor of b and b
is a descendant of a.

30
 Trees: Edges in a Tree
• Theorem : A tree on n vertices has n–1 edges.
Proof: Let T be a tree with n vertices. Make it rooted.
Then every edge establishes a parent-child relationship
between two vertices. Every child has exactly one
parent, and every vertex except the root is a child.
Therefore there is exactly one edge for each vertex but
one. This means there are n–1 edges.

31
 Trees: Edges in a Tree
• Theorem : If G(V,E) is a connected graph with n vertices
and n–1 edges is a tree.
Proof: Suppose G is as in the statement of the theorem,
and suppose G has a cycle. Then we can remove an edge
from the cycle without disconnecting G (see the next
slide for why). If this makes G a tree, then stop. If not,
there is still a cycle, so we can remove another edge
without disconnecting G. Continue the process until the
remaining graph is a tree. It still has n vertices, so it has
n–1 edges by a prior theorem. This is a contradiction
since G had n–1 vertices to start with. Therefore G has
no cycle and is thus a tree.
32
 Trees: Edges in a Tree (lemma)
• (Why can we remove an edge from a cycle without
disconnecting the graph? Let a and b be vertices. There
is a simple path from a to b. If the path involves no edges
in the cycle, then the path from a to be is unchanged. If it
involves edges in the cycle, let x and y be the first and
last vertices in the cycle that are part of the path from a
to b. So there is a path from a to x and a path from y to b.
Since x and y are part of a cycle, there are at least simple
two paths from x to y. If we remove an edge from the
cycle, at least one of the paths still remains. Thus there is
still a simple path from a to b.)

33
 Spanning Trees of a Graph
• If G(V,E) is a graph and T(V,F) is a subgraph of G and is
a tree, then T is a spanning tree of G. That is, T is a tree
that includes every vertex of G and has only edges to be
found in G. Using the procedure in the previous
paragraph (remove edges from cycles until only a tree
remains), we can easily prove that every connected graph
has a spanning tree (theorem 6.43).

34