Graph Theory

Graph Theory was developed by Leonhard Euler to solve the 7 bridges of Konigsberg problem.

A graph $G$ is a collection of vertices, $V$, and edges, $E$.

So we say $G = <V,E>$

Here is an example of a graph:

Incident - Edges that touch a vertex. Ex. $x$ is incident to $a$ and $b$.

Adjacent - Vertices that are connected. Ex. $a$ is adjacent to $b$; $b$ is adjacent to $a,c,e$

Isolated - Vertices that are not connected. Ex. $d$ is isolated.

The are two types of graphs, undirected and directed. In a directed graph, order matters.

There are two types of “walks”. X-Y walks and closed walks.

def: the number of edges incident to a node is called the degree of a node.