Graph Theory: Paths and Circuits

Isomorphism

Two graphs are thought of as equivalent and are called isomorphic if they have identical behavior in terms of graph theoretic properties.

Two graphs G and G' are said to be isomorphic to each other if there is one-to-one correspondence between their vertices and between their edges such that the incidence relationship is preserved.

In other words suppose that edge e is incident on vertieces v₁ and v₂ in G; then corresponding edge e' in G' must be incident on the vertices v₁' and v₂' that correspond to v₁ and v₂ respectively.

Two isomorphic graphs must have:

1. The same number of vertices.

2. The same number of edges.

3. And equal number of vertices with a given degree.

These conditions are by no means sufficient. Finding simple and efficient criteria for detection of isomorphism is still actively pursued and is an important unsolved problem in graph theory.

Subgraph

Graph Theory: Introduction

Your browser does not support the canvas element.

Graph Definition

Graph is a collection of edges and vertices.

G = (V, E)

V is set of vertices and E is set of edges.

Each edge is identified with pair of vertices (v_i, v_j).

Vertices associated with edge ek are called the end vertices of e_k.

A vertex is also referred to as node, junction, point.

Other terms used for an edge are a branch, a line, an element.

Loop

An edge having the same vertex as both its end vertices is called as self loop or simply a loop.

Parallel Edges

Edges having same pair of vertices as their end veritices are called parallel edges.

Simple Graph

A graph that has neither self loops nor parallel edges is called simple graph.

Incidence

When a vertex v_i is n end vertex of some edge e_j, v_i and e_j are said to be incident to each other.

Adjacent

Two non-parallel edges are said to be adjacent if they are incident on a common vertex.

Two vertices are said to be adjacent if they are the end vertices of the same edge.

Degree of a vertex

The number of edges incident on a vertex v_i with self lopps counted twice is called the defree d(v_i) of vertex v_i.

Degree of vertexd is sometimes also referred to as its valency.

Hand Shaking Theorm

Since each edge contributes two degrees, the sum of the degrees of all vertices in graph G is twice the number of edges in G.

Sum(deg(v_i)) { for i = 1 to n } = 2 . e

n = number of vertices.

e = number of edges.

Theorm 1.1

The number of vertices of odd degree in a graph is always even.

sum of degrees of all vertices = sum of degrees of vertices with even degrees + sum of degrees of vertices with odd degree

Left Hand Side is even number. The first term in Right Hand Side is even number. So the second term in RHS also needs to be an even number. Hence the theorm.

Regular Graph

A graph in which all vertices are of equal degree is called a regular graph.

Isolated vertex

A vertex having no incident edge is called an isolated vertex. Isolated vertices are vertices with zero degrees.

Pendant Vertex

A vertex of degree one is called a pendant vertex or an end vertex.

Edges in series

Two adjacent edges are said to be in series if their common vertex is of degree two.

Null Graph

A graph without any edges is called a null graph. Every vertex in a null graph is an isolated vertex.