> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/graph_theory.md).

# graph theory

## Basic idea

Graph theory studies pairwise relationships using vertices and edges. In computer science, graphs model networks, dependencies, control flow, state spaces, dataflow, programs, and distributed systems.

## Key formulas

* Graph: $G=(V,E)$; directed edges satisfy $E\subseteq V\times V$.
* Handshaking lemma: $\sum\_{v\in V}\deg(v)=2|E|$ for an undirected graph.
* Adjacency matrix: $A\_{ij}=1$ when edge $(i,j)$ exists.
* Path reachability is the transitive closure of the edge relation.
* A tree is a connected acyclic graph and has $|E|=|V|-1$.
* Euler characteristic for a connected planar graph: $|V|-|E|+|F|=2$.