5 Graph Theory

❖ Definition of Graph

• Graph (): Consists of two fundamental elements: Vertices () and

Edges ().

• Vertices: These are the points or nodes in a graph, typically

represented visually as circles (V1,V2, etc.).

• Edges: These are the lines that connect the vertices (E1,E2, etc.).
❖ Types of Graphs

• Trivial Graph: A graph that contains only one vertex and

zero edges.
• Example

• Null Graph: A graph that has multiple vertices, but no edges

are present.
• Example

• Self Loop: An edge that starts and ends at the exact same
vertex.
• Example
• Multi Edge (Multiple Edges): Two or more distinct edges
that connect the same pair of vertices (sharing the same end
points).

• Directed Graph: A graph where each edge has a specific

direction assigned to it, showing a path from one vertex to
another.

•
• Simple Graph: A graph that does not contain any self loops
or multi edges.

• Multi Graph: A graph that contains multiple edges between

vertices.

• Weighted Graph: A graph where a numerical value or

weight (such as distance in kilometers) is assigned to each
edge.
•

• Complete Graph: A graph where every single vertex is

directly connected to every other vertex.

• Regular Graph: A graph in which every vertex has the

exact same degree (for example, if every vertex has exactly
2 connecting edges, it is a regular graph).

•
o Degree of vertex :

o In-degree and Out degree

 o Isolated vertex : vertex = degree 0.
o Pendant Vertex: vertex = degree 1.

➔ Find degree of vertex :

❖ Directed Graphs

A directed graph is a graph where each edge has a specified,

unidirectional orientation.

• Edges are represented as ordered pairs of vertices. Relationships are

asymmetric: an edge does not imply
 Examples :

❖ Representation of Graphs using Matrices

1. Adjacency Matrix

The Adjacency Matrix focuses entirely on the relationships between the vertices (nodes) of the graph. For a
graph with vertices, the matrix is of size , where both rows and columns represent the vertices (such as ).

Undirected Graphs:

If vertex is connected to vertex by an edge, you write at the intersection of row and column . If there is no
connection, you write .

Self-Loops: If a vertex has a self-loop (an edge connecting back to itself), you write at its diagonal position
(e.g., row , column ). If there is no self-loop, the diagonal element remains .

Multi-Edges (Parallel Edges): If two vertices are connected by more than one edge, you write the exact
count of those edges instead of just . For instance, if connects to twice, you record a in that cell.

Directed Graphs (Digraphs):

You must pay close attention to the direction of the arrows.

You only record outgoing edges (arrows pointing away from the vertex) as .

Incoming edges (arrows pointing into the vertex) are ignored for that specific vertex's row and are
represented as .

o Adjacency Matrix Examples :

1) Find Adjacency Matrix :

2)Find Adjacency Matrix :

3)Find Adjacency Matrix

4)Find Adjacency Matrix

5) Drow the graph corresponding to each Adjacency Matrix :

2. Incidence Matrix
The Incidence Matrix represents the relationships between vertices and edges. In this matrix, the rows
correspond to the vertices () and the columns correspond to the edges ().

Undirected Graphs:

If an edge is connected (incident) to a vertex , you write at row , column .

If the edge is not connected to that vertex, you write .

Directed Graphs (Digraphs):

For directed graphs, the incidence matrix tracks both incoming and outgoing directions.

Outgoing Edge (Out): If the edge is directed away from the vertex , it is represented as .

Incoming Edge (In): If the edge is directed into the vertex , it is represented as .

If the edge is not incident to the vertex at all, it is represented as .

Reversing the Process: Drawing a Graph from a Matrix

Just as you can extract a matrix from a graph, you can also draw a graph from a given matrix.

In an adjacency matrix, a at cell tells you to draw an edge between vertex and vertex .

In a directed incidence matrix, a indicates an incoming arrow pointing toward that vertex, while a indicates
an outgoing arrow pointing away from it. If a vertex is connected to itself, a diagonal in the adjacency matrix
translates to drawing a self-loop
Examples :
1)Find Incidence Matrix

2) Find Incidence Matrix :

 2) Find Incidence Matrix :
(Note : In = -1 And Out =1)

❖ Connected and Disconnected Graphs

1)Connected Graph
A graph is connected if there exists a path between any two vertices in the graph. In
other words, starting from any vertex, you can reach every other vertex by traversing
edges.
 The following table shows the paths between all pairs of vertices in the connected
graph above −

Vertex 1 Vertex 2 Path(s)

a b a→b

a c a → b → c, a → c

a d a → b → c → d, a → c → d

b c b → a → c, b → c

c d c→d

Every pair of vertices has at least one path between them, so the graph is
connected.

2)Disconnected Graph
A graph is disconnected if at least two vertices are not connected by any path. If a
graph G is disconnected, then every maximal connected subgraph of G is called
a connected component of the graph G.
The following table shows the paths between vertex pairs in the disconnected graph above −

Vertex 1 Vertex 2 Path(s)

a b a→b

a c Not Available

a d Not Available

b c Not Available

c d c→d

Several vertex pairs (such as a–c, a–d, and b–c) have no path between them, so the graph is disconnected.

This graph has two connected components − one containing vertices {a, b} and another containing vertices
{c, d}.

❖ Sub graphs
In graph theory, a subgraph is a graph formed from a subset of the vertices and edges of another
graph. Subgraphs plays an important role in understanding the structure and properties of larger
graphs by examining their smaller, constituent parts.
Sub graphs :

❖ Bipartite Graphs
A bipartite graph is a network of dots and lines whose dots can be split into two separate groups. No
two dots in the same group connect with a line. Every line goes from a dot in the first group to a dot
in the second group.

OR
❖ Paths and Cycles

➢ Path
A path is a trail in which neither vertices nor edges are repeated.
In other words, when traversing a graph along a path, each vertex and each edge is visited exactly
once. Since a path is also a trail, it is inherently an open walk unless stated otherwise.
Another definition of a path is a walk with no repeated vertices. This automatically implies that no
edges are repeated, making it unnecessary to explicitly mention edge repetition in the definition.
Key characteristics of a path:
• Vertices are not repeated.
• Edges are not repeated.

Here 6->8->3->1->2->4 is a Path

 ➢ Cycle
A cycle in graph is a closed path, meaning that it starts and ends at the same vertex while ensuring
that no other vertices or edges are repeated.
In other words, a cycle is formed by traversing a graph such that: No vertex is repeated, except for
the starting and ending vertex, which must be the same and No edge is repeated.
Key characteristics of a cycle:
• Edges cannot be repeated.
• Vertices cannot be repeated, except for the first and last vertex, which must be the
same.

Here 1->2->4->3->1 is a cycle.

❖ Graph Isomorphism
The Four Conditions of Graph Isomorphism :

1. Same Number of Vertices: Both graphs must have the exact same number of vertices.

2. Same Number of Edges: Both graphs must contain the exact same number of edges.

3. Same Degree Sequence: The sorted list of vertex degrees must be identical in both graphs.

4. One-to-One Correspondence (Bijection): There must be a valid mapping of vertices and

edges between the two graphs. If a vertex maps to , then their connections (adjacencies) and
corresponding degrees must behave identically

Example 1:
 - Both the graphs have the same number of edges.
- The graphs are NOT isomorphic.

Example 2:
Example 3:

• Vertices = 4
• Edges = 5
• Degree sequence = 3, 3, 2, 2
• One-to-One Correspondence =
a → v₁
b → v₂
c → v₄
d → v₃

→ G₁ and G₂ are isomorphic graphs because they have the same number of vertices, same number
of edges, same degree sequence (3,3,2,2), and their corresponding vertices have the same adjacency
relationship.

Example 4:

• Vertices = ?
• Edges = ?
• Degree sequence = ?
• One-to-One Correspondence = ?

Are the given graphs isomorphic or non-isomorphic?

Example 5: Are the given graphs isomorphic or non-isomorphic?

❖ Euler and Hamiltonian Paths

• Eulerian is strictly about covering Edges.

• Hamiltonian is strictly about visiting Vertices.

1. Euler (Focus: Edges)

When working with Eulerian concepts, you must use every single edge in the graph exactly once. No edge
can ever be repeated.

• Euler Path: A trail that visits every edge of the graph exactly once.
Example 1 :
Example 2:
Example 3:

2. Hamiltonian (Focus: Vertices) :

When working with Hamiltonian concepts, you must visit every single vertex in the graph exactly
once.

• Hamiltonian Path: A path that visits every vertex in the graph exactly once.

Example :
Example 1:

Example 2:
❖ Planar Graphs
A graph is said to be planar if it can be drawn on a flat plane in such a way that no edges cross (or intersect)
one another. If a graph is originally drawn with crossing edges, but can be redrawn without any crossings, it
is still considered a planar graph.

Example 1:

Example 2: