Graph Theory

Some Notions
● Path in an undirected graph G = (V, E): A sequence P of nodes v1,
v2 ... vk-1, vk with the property that each consecutive pair vi, vi+1 is
joined by an edge in G.
– P is often called a path from v1 to vk. For example, the nodes 4, 2,
1, 7, 8 form a path in below figure
● A path is called simple if all its vertices are
distinct from one another.
● A cycle is a path v1, v2 ... vk-1, vk in which k > 2,
the first k – 1 nodes are all distinct, and v1 = vk
● All of these definitions carry over naturally to directed graphs, with the
fol!owing change: in a directed path or cycle, each pair of consecutive
nodes has the property that (vi, vi+1) is an edge (the sequence of
nodes in the path or cycle must respect the directionality of edges).
Some Notions
● Walk: a walk is an alternating sequence of vertices and edges:
v0e1v1e2...ekvk
such that each edge ei connects the vertex vi-1 to vi.
– In a walk, vertices and edges may repeat any number of times.
– The length of a walk is the number of edges it contains
– Open and Closed walk
● Open Walk: A walk is said to be open if the starting vertex and the
ending vertex are different.
● Closed walk: A walk is said to be closed if the starting vertex and the
ending vertex are the same.
Some Notions
● Trail: a type of walk in a graph such that No edge is repeated and
Vertices may repeat.
● Open Trail: A trail is considered an open trail if the starting and
ending vertices are different.
● Closed Trail: A trail is a closed trail if the starting and ending vertices
are the same.
● Circuit: A Closed Trail
●
Path: a special type of walk where no vertex is repeated (and hence
no edge is repeated)
– Also, a path is a trail in which neither vertices nor edges are repeated.
● Open Path: starts and ends at different vertices.
● Closed Path: starts and ends at the same vertex and no other vertex
is repeated : Also called a cycle.
Some Notions
● Cycle: A special type of path where the starting
and ending vertex are the same, and no other
vertex or edge is repeated.
●
Euler Graph
● Leonhard Euler: Königsberg Bridge Problem,”
concerns the town of Königsberg in Prussia (now
Kaliningrad in Russia): to find a walk through town that
crossed each of the seven bridges once and only once
(and, hopefully, ended where it started). Is such a
walk possible?
Euler Graph
● Let us get a graph to replace the schematic map of Königsberg
● In graph theoretic terminology Euler’s question asks whether there is
a path, starting and ending at the same vertex, that uses each edge
exactly once.

no such walk is
possible. Why?
such a walk will enter a land mass on a bridge and leave it on a different bridge, so
except for the starting and ending point, the walk requires two new bridges each time it
enters and leaves a land mass. Thus each of these land masses must be at the end of
an even number of bridges.
Euler Graph
● Any connected graph is called as an Euler
Graph if and only if all its vertices are of even
degree.
– OR
● An Euler Graph is a connected graph that
contains an Euler Circuit.
Euler Path
● Euler path is also known as Euler Trail or Euler
Walk.
● If there exists a Trail in the connected graph
that contains all the edges of the graph, then
that trail is called as an Euler trail.
OR
● If there exists a walk in the connected graph
that visits every edge of the graph exactly once
with or without repeating the vertices, then such
a walk is called as an Euler walk.
Euler Path
Euler Circuit
● Euler circuit is also known as Euler Cycle or Euler Tour.
● If there exists a Circuit in the connected graph that contains all the
edges of the graph, then that circuit is called as an Euler circuit.
OR
● If there exists a walk in the connected graph that starts and ends at
the same vertex and visits every edge of the graph exactly once with
or without repeating the vertices, then such a walk is called as an
Euler circuit.
OR
● An Euler trail that starts and ends at the same vertex is called as an
Euler circuit.
OR
● A closed Euler trail is called as an Euler circuit.
Euler Circuit
● A graph will contain an Euler circuit if and only
if all its vertices are of even degree.
Semi-Euler Graph
● If a connected graph contains an Euler trail but does not
contain an Euler circuit, then such a graph is called as a
semi-Euler graph.
● Thus, for a graph to be a semi-Euler graph, following two
conditions must be satisfied
– Graph must be connected.
– Graph must contain an Euler trail
● The given graph contains an Euler trail BCDBAD.
– But it does not contain an Euler circuit
Important Notes
● Note-01: To check whether any graph is an Euler graph or not, any
one of the following two ways may be used:
– If the graph is connected and contains an Euler circuit, then it is
an Euler graph.
– If all the vertices of the graph are of even degree, then it is an
Euler graph.
● Note-02: To check whether any graph contains an Euler circuit or not,
– Just make sure that all its vertices are of even degree.
– If all its vertices are of even degree, then graph contains an Euler
circuit otherwise not.
● Note-03: To check whether any graph is a semi-Euler graph or not,
– Just make sure that it is connected and contains an Euler trail.
– If the graph is connected and contains an Euler trail, then graph is
a semi-Euler graph otherwise not.
Important Notes
● Note-04: To check whether any graph contains an Euler trail or not,
– Just make sure that the number of vertices in the graph with odd
degree are not more than 2.
– If the number of vertices with odd degree are at most 2, then
graph contains an Euler trail otherwise not.
●
Note-05:
– A graph will definitely contain an Euler trail if it contains an Euler
circuit.
– A graph may or may not contain an Euler circuit if it contains an
Euler trail.
● Note-06:
– An Euler graph is definitely be a semi-Euler graph.
– But a semi-Euler graph may or may not be an Euler graph
Practice Problems- Which of the
following graphs are Euler Graph?
Practice Problems- Which of the
following graphs are Euler Graph?
Practice Problems- Solution
Bipartite Graphs
● An undirected graph G = (V, E) is said to
be bipartite if the set of vertices V can be
partitioned into two disjoint subsets V1
and V2 such that every edge (u, v) ∈ E
satisfies one of the following conditions:
– u ∈ V1 and v ∈ V2, or
– u ∈ V2 and v ∈ V1.
● In other words, edges in the graph
connect a vertex from one set to a vertex
from the other set
– no edge exists between two vertices
within the same subset.
● How to check if any given graph is
bipartite?
Bipartite Graphs
● How to check if any given graph is bipartite?
● Let us color the nodes in the set V1 red, and
the nodes in the set V2 blue.
● Using this, we can say a graph is bipartite if it
is possible to color its nodes red and blue so
that every edge has one red end and one blue
end.
● Using this can we say that a triangle is
bipartite graph?
● Extending this to a general cycle with odd
length- is it a bipartite graph?
● More generally,
– If a graph G is bipartite, then it cannot
contain an odd cycle.
Breadth First Search
Bipartite Graph and BFS
● To check whether a graph G is bipartite? :
All we need to do is to determine whether there
exists a partition into red and blue nodes, as
required.
● How to do this and how difficult is this?
● We saw from previous result that an odd cycle
is one simple "obstacle" to a graph's being
bipartite.
● Are there other, more complex obstacles to
bipartitness: We can show that odd cycles are
the only obstacle.
Bipartite Graph and BFS
● First we assume the graph G is connected (otherwise we can first
compute its connected components and analyze each of them
separately.)
● Next we pick any node s ~ V and color it red.
– It follows that all the neighbors of s must be colored blue.
– It then follows that all the neighbors of these nodes must be
colored red, their neighbors must be colored blue, and so on, unti!
the whole graph is colored.
● At this point, either we have a valid red/blue coloring of G, in which
every edge has ends of opposite colors, or there is some edge with
ends of the same color.
– In this latter case, G simply is not bipartite.
●
What is an efficient way to perform the coloring.?
Bipartite Graph and BFS
●
What is an efficient way to perform the coloring.?
● In the coloring procedure we have just described essentially that is
identical to the description of BFS:
– we move outward from s, coloring nodes as soon as we first
encounter them.
– We perform BFS, coloring s red, all of layer L1 blue, all of layer L2
red, and so on, coloring odd-numbered layers blue and even-
numbered layers red.
● Thus, the total running time for the coloring algorithm is O(m + n).