Graph

Graph

A Graph is a non-linear data structure that represents a set of nodes (vertices) and links (edges) between them.
It is denoted as:

where:

• V = set of vertices

• E = set of edges

Connected Graph

A graph $G(V,E)$ is said to be connected if there exists at least one path between every pair of distinct vertices of the graph.

Path

A path in a graph is a sequence of edges that connects a source vertex to a destination vertex.

Hamiltonian Circuit (Cycle)

A Hamiltonian Circuit is a cycle in a graph that:

• Passes through each vertex exactly once, and

• Returns to the starting vertex (terminal one)

If a graph $G(V,E)$ contains a Hamiltonian circuit, then the graph is called a Hamiltonian Graph.

Tree

A Tree is a connected graph without any cycle.

• Acyclic + Connected = Tree

• A tree with n nodes has (n − 1) edges

Spanning Tree

A Spanning Tree is a subgraph of a connected graph $G(V,E)$ that:

• Includes all the vertices of $G$

• Contains no cycles

• Is a tree

Let $G(V,E)$ be a connected graph. A graph $H(V^{\prime },E^{\prime })$ is a Spanning Tree of G if:

$H$ is a subgraph of $G$

1. $H$ is a Tree
   (Connected and acyclic)

2. $V^{\prime }=V$
   (All vertices of G must be in H)