Go back to UGC NET COMUPTER SCIENCE
GRAPH THEORY
(Groups, Subgroups, Semi Groups, Product and Quotients of Algebraic, Structures, Isomorphism, Homomorphism, Automorphism, Rings, Integral Domains, Fields, Applications of Group Theory)
1. SIMPLE GRAPH
Definition
A simple graph is a graph in which:
-
There is at most one edge between any pair of vertices.
-
There are no loops (no edge from a vertex to itself).
A simple graph consists of:
-
: Set of vertices
-
: Set of unordered pairs of distinct vertices
Example
Vertices: {A, B, C}
Edges: {AB, BC}
No loops, no parallel edges → simple graph.
2. MULTIGRAPH
Definition
A multigraph is a graph where:
-
Multiple (parallel) edges between the same pair of vertices are allowed.
-
Loops may or may not be allowed (depending on the author).
Example
Two edges between A and B → multigraph.
3. WEIGHTED GRAPH
Definition
A weighted graph assigns a numerical value (weight) to each edge.
Weights represent:
-
distance
-
cost
-
time
-
capacity
Example
A triangle graph with edges weighted 1, 3, 4.
4. PATHS AND CIRCUITS
Definition: Path
A path in a graph is a sequence of distinct vertices where every consecutive pair is connected by an edge.
Example:
A → B → D → E
Definition: Circuit (Cycle)
A circuit is a path that begins and ends at the same vertex, with no repeated edges.
Example:
A → B → C → A
5. SHORTEST PATHS IN WEIGHTED GRAPHS
Definition
A shortest path between two vertices is the path with minimum total weight.
Algorithm (important for NET)
-
Dijkstra’s Algorithm: For non-negative weights
-
Bellman–Ford: For negative weights
Example
If A→B=3 and A→C→B=1+1=2,
shortest path from A to B is A → C → B.
6. EULERIAN PATHS AND CIRCUITS
Definition: Euler Path
A path that uses every edge exactly once.
Definition: Euler Circuit
A circuit that uses every edge exactly once and returns to the starting vertex.
Theorems (Very important)
Euler Circuit Theorem
A connected graph has an Euler circuit iff every vertex has even degree.
Euler Path Theorem
A connected graph has an Euler path iff exactly 0 or 2 vertices have odd degree.
7. HAMILTONIAN PATHS AND CIRCUITS
Definition: Hamiltonian Path
A path that visits every vertex exactly once.
Definition: Hamiltonian Circuit
A Hamiltonian path that returns to the starting vertex.
Key Notes
-
No simple degree condition like Euler.
-
Hamiltonian problems are NP-complete.
Example
Cycle graph is Hamiltonian (n ≥ 3).
8. PLANAR GRAPH
Definition
A graph is planar if it can be drawn on a plane without edge crossings.
Euler’s Formula (Very important)
For a connected planar graph:
Where
-
V = vertices
-
E = edges
-
F = faces (regions)
9. GRAPH COLORING
Definition
Graph coloring assigns colors to vertices so that adjacent vertices have different colors.
Chromatic Number (χ(G))
Minimum number of colors needed.
Example
A triangle (3-cycle) needs 3 colors:
10. BIPARTITE GRAPHS
Definition
A graph is bipartite if its vertices can be divided into two sets U and V such that:
-
Every edge connects a vertex in U to a vertex in V
-
No edge connects two vertices within the same set.
Theorem
A graph is bipartite iff it has no odd cycle.
Example
A square (4-cycle) is bipartite.
11. TREES
Definition
A tree is a connected graph with no cycles.
Equivalent statements:
-
A tree with n vertices has n−1 edges.
-
Exactly one path exists between every pair of vertices.
-
Removing any edge disconnects the tree.
12. ROOTED TREES
Definition
A rooted tree is a tree with one vertex chosen as root.
Terms used:
-
Parent
-
Child
-
Sibling
-
Ancestor
-
Descendant
-
Level / Depth
-
Height
13. PREFIX CODES
Definition
A prefix code is a set of binary strings where no code word is a prefix of another.
Used in data compression (Huffman coding).
Example
Valid: {0, 10, 110, 111}
Not valid: {0, 01} (0 is a prefix of 01)
14. TREE TRAVERSALS
Definition
Tree traversal means visiting nodes of a tree in a specified order.
1. Preorder Traversal
Root → Left → Right
2. Inorder Traversal
Left → Root → Right
3. Postorder Traversal
Left → Right → Root
15. SPANNING TREES
Definition
A spanning tree of a connected graph G is a subgraph that:
-
includes all vertices,
-
is a tree (no cycles),
-
has minimum possible edges (n−1).
Minimum Spanning Tree (MST)
Spanning tree with minimum total weight.
Algorithms
-
Prim’s Algorithm
-
Kruskal’s Algorithm
16. CUT-SETS
Definition
A cut-set is a set of edges whose removal disconnects the graph.
Example
In a triangle graph, removing any two edges forms a cut-set.