Graph Theory
Introduction
• ‘Graph’ refers to a structure consisting of points (vertices), and some
may be joined to the other points (vertices) by lines (edges) to form a
network
• Examples: Computers connected to a local network which in turn is
connected to a wider network including Internet
Circuitry inside a computer is another example of graph or
network structure
• e1 to e6 are called EDGES
• V1 to V5 are called VERTICES
• An edge is incident to vertices to which it is
attached
• E1 is incident to V1 & V2
• V1 & V2 are adjacent
• Some examples of vertices: Computers in a
LAN, Towns
• Some examples of edges: Links in the network,
roads
What is allowed and what is not!
• There is no limit or restriction to the number of vertices or edges a graph may have
• Graphs might have NO EDGES (i.e. only vertices). In this case, they are called NULL
Graph.
• Graphs may have loops or parallel edges. If it does not have any loops or parallel edges,
it is termed to be SIMPLE
• Precise location of vertices, lengths and shapes of the edges are not relevant
• Graphs can be rearranged (move vertices, stretch & bend edges), we should not create
new edges or vertices
• Graphs can be regenerated by moving vertices and edges around (then they would be
ISOMORPHIC)
Some examples
**All these graphs are isomorphic. As the there is no breaking or rejoining edges or
creating new edge involved.
A simple graph with 3 vertices!
All these graphs are different from each other as there are different number of edges.
Any graph with 3 vertices are isomorphic to any one of the above!
*Practice drawing possible graphs with 4 or 5 vertices and see how many types can you
generate!
Degree of a Vertex!
** In any graph, the sum of degrees of the vertices is equal to twice the number of edges
Example
Adjacency Matrix
• For graphs to be handled by computer, it needs to be represented in a matrix form.
This matrix is called adjacency matrix.
• Example: Construct adjacency matrix for this graph with vertices in order a,b,c,d,e
• Values in the matrix represent the number of edges between those two vertices
• A graph with n vertices can have n! different ways to arrange them. So there will be that many
adjacency matrices
Key terminology!
• Order of the graph→ number of vertices to be existent
• Adjacent vertex→ vertices with common edge
• Multi-edges/Parallel Edges: More than one linkage between a pair
of vertices
• Pseudograph: A graph that allows self-loop and multiple edges
between two vertices
• Multigraph: A graph that contains only parallel edges
• Simple graph: Every vertex has same degree, NO self-loop and
multiple edges
• Regular graph: graph in which every vertex has same degree
• Complete graph: a simple graph where each vertex is adjacent to
each other
Review Question!
• For the following graph, find the degree of each vertex and the number
of edges. Please comment on the following statement:
‘The quantity of vertices with odd number of degrees is always even’
A B
C D
E
Check for Isomorphs!
• Check the number of vertices and edges: If two graphs have a different number
of vertices or edges, then they cannot be isomorphic.
• Check the degrees of the vertices: If two vertices in one graph have different
degrees than the corresponding vertices in the other graph, then the graphs
cannot be isomorphic.
• Degree sequence: Write the degrees of each vertex in sequence and try to match
them, if the values are similar the sequence is to be checked by shuffling
• Mapping: Try to map vertices from one graph to the other graph with similar
edges and
• Validation: Once the vertices are mapped, check for the edge formation
Example
• Check whether each pair of graphs are isomorphic or not
t
A B
D C v u
No. of vertices: G1→4, G→4
No of edges: G1→5, G1→5
Degree of vertices: G1→2, 3, 2, 3 & G2→2, 3, 2, 3
Mapping: a→t, b→u, c→w, d→v
Validation: abcd & tuwv
Practice Problem
• Justify whether these two graphs are isomorphs or not:
A
1
E B 5 2
4 3
D C
Practice Problem
Justify whether these two graphs are isomorphs or not
Practice Problem
• What is the complement of the following graph
Practice Problem
Practice Problem
Practice Problem
Practice Problem
21
Types of Simple Graph
• Null graph: A graph with ‘n’ vertices and zero edges
• Cyclic graph (Cn, n>=3): A simple graph with ‘n’ vertices {V1,
V2, ….Vn} and edges {V1,V2}; {V2,V3};{V4,V5}…..{Vn,V1}
• Bipartite graph, G={V,E} is if the vertex set can be
partitioned into sets V1 and V2 such that every edge is in
between a vertex V1 to V2
Euler Paths and Circuits
• An Euler path is a path using every edge of the
graph G exactly once. Covers all edges without
repetition from one point to another
• An Euler circuit is an Euler path that returns to its
C
start.
Does this graph have an
A D
Euler circuit?
B
Necessary and Sufficient Conditions
• How about multigraphs?
• A connected multigraph (has at least one path
between every pair of vertices) has a Euler circuit
iff each of its vertices has an even degree.
• A connected multigraph has a Euler path but not an
Euler circuit iff it has exactly two vertices of odd
degree.
Example
• Which of the following graphs has an
Euler circuit?
a b a b a b
e e
d c d c c d e
yes no no
(a, e, c, d, e, b, a)
Example
• Which of the following graphs has an Euler
path?
a b a b a b
e e
d c d c c d e
yes no yes
(a, e, c, d, e, b, a ) (a, c, d, e, b, d, a, b)
Practice Questions
Find if these graphs contain Euler path or Euler circuit.
Hamilton Paths and Circuits
• A Hamilton path in a graph G is a path which
visits every vertex in G exactly once.
• A Hamilton circuit is a Hamilton path that
returns to its start.
Finding Hamilton Circuits
Which of these three figures has a Hamilton circuit? Of, if
no Hamilton circuit, a Hamilton path?
Finding Hamilton Circuits
• G1 has a Hamilton circuit: a, b, c, d, e, a
• G2 does not have a Hamilton circuit, but does have a Hamilton
path: a, b, c, d
• G3 has neither.
Practice Problem
Hamiltonian Path? Hamiltonian Circuit? Both? Neither?
A Sufficient Condition for Hamiltonian Circuit
Let G be a connected simple graph with n vertices with n 3.
If the degree of each vertex is n/2,
then G has a Hamilton circuit.
Checkpoint!
• A connected graph is semi-Eulerian if and only if precisely
two of its vertices have odd degree.
• To obtain a semi-Eulerian trail in each graph, you must start at
one of the odd degree vertices and end in the other odd degree
vertex.
Summary
Property Euler Hamilton
Repeated visits to a given Yes No
node allowed?
Repeated traversals of a No No
given edge allowed?
Omitted nodes allowed? No No
Omitted edges allowed? No Yes