**Graphs**

An undirected graph is given by vertices and edges where for every pair . This is usually expressed as . A directed graph is given by vertices and arcs . This is expressed as .

**Some questions on graphs**:

- Given , does there exist a path between .
- Shortest path between .
- Find largest clique in .
- Does have a Hamiltonian cycle?
- Find chromatic number of .

**Connected components of a graph**

Given a graph in either the adjacency matrix or adjacency list representation, find the connected components of . A subset is a *connected component *of if for every there is a path in from to and for every there is no path from any to .

One possible way to do it is using Depth First Search (DFS). We can write this recursively as:

:

- Initialize
- For every such that and , include in and call .

The output of would give us the connected component of that contains . To obtain a list of connected components one can pick a vertex such that , run and iterate till such a cannot be found.