# Graph Theory

Graph theory is the study of mathematical structures used to model relations between objects

## Undirected Graphs

An undirected graph is defined as a tuple containing a set of vertices and a set of edges, where the vertices correspond to the graph nodes, and the edges correspond to the connections between them.

For example: \((\{ A, B, C \}, \{ \{ A, B\}, \{ A, C \} \})\) is a graph which three nodes, where A is connected to B and C.

Notice that the edges are declared by unordered sets, therefore we call these
kinds of graph *undirected*.

Undirected graphs donâ€™t have the concept of more than one edge between a set of vertices, therefore the edges must be a set, and not a multi-set.

### Degree

The degree of a vertex is the number of edges incident to such vertex. Formally, \(degree(u) = |\{ v \in V | \{ v, u \} \in E \}|\). A vertex whose degree is 0 is called an isolated vertex.

## Directed Graphs

A directed graph is similar to an undirected graph with the addition of encoding the direction of the edges. A directed graph consists of a set of vertices and a set of edges containing tuples instead of other sets. For example: \((V, E)\) where \(V = \{ A, B \}\) and \(E = \{ (A, B) \}\) denotes a directed graph where A is connected to B, but B is not connected to A, since \((B, A) \notin E\).

If each edge goes in both directions, then the graph is undirected.

### Degree

Directed graphs have two types of degrees. The **in-degree** of a vertex is the
number of edges *to* that vertex. The **out-degree** of a vertex is the number
of edges *from* that vertex to other vertices.

## Incidence

If an edge connects vertices A and B, then we say such vertices are
*neighbors*, or *adjacent*. We also say that such edge is *incident* on A and
B.

## Self-loops

An edge from a node to itself is called a self-loop.

## Subgraphs

A graph is a subset of another graph if its nodes and edges are subsets of the
other graph. Given graphs \(G_{1} = (E_{1}, P_{1})\) and \(G_{2} =
(E_{2}, P_{2})\), \(G_{1}\) is a *subgraph* of \(G_{2}\) if \(E_{1}
\subseteq E_{2}\) and \(P_{1} \subseteq P_{2}\).

## Paths

A path is a sequence of neighbor edges in a graph that goes from vertices A to B. Given \((\{ A, B, C \}, \{ \{ A, B\}, \{ A, C \} \})\), a valid path from B to C would be \((\{ B, A \}, \{ A, C \})\).

A path is *simple* if the starting and ending vertices are different. A
**cycle** is a path which starts and ends in the same vertex.

A path from A to B with repeated edges is called a *walk* from A to B. A *tour*
is a walk that starts and ends on the same vertex.

A walk that that uses each edge exactly once is called an Eulerian walk. If such walk starts and ends on the same vertex, then its called an Eulerian tour.

## Properties

### Connected

A graph is said to be connected if there is a path between any two distinct vertices. Notice that even a disconnected graph consists of a collection of connected components.

### Even Degree

A graph in which all vertices have even degrees.

### Planar

A graph is planar if it can be drawn without overlapping edges.

TODO: How do we mathematically check this?

### Complete

A complete graph contains the maximum number of edges possible. For every pair
of distinct vertices, there exists an edge between then. We say that a complete
graph is *strongly connected*. In the case of directed graphs, for every pair
of vertices \(u\) and \(v\) the graph contains two edges: \((u, v)\) and
\((v, u)\).

\(K_{n}\) denotes the unique complete graph on \(n\) vertices. The number of edges in \(K_{n}\) is \(n \times \frac{(n - 1)}{2}\). The degree of any vertex in \(K_{n}\) is \(|V| - 1\).

## Trees

A tree is a connected acyclic graph. Its a minimally connected graph, the
opposite of a complete graph, and the most effective graph we can use to
connect any set of vertices. A tree has \(|V| - 1\) number of edges. A node
with a degree of 1 is called a *leave*.

Removing any single edge disconnects the graph and adding any single edge creates a cycle.

### Rooted Trees

A rooted tree is a tree with a designated *root node*. The botton-most nodes
are called *leaves*, and the intermediate nodes are called *internal nodes*.

The depth of a tree is determined by the length of the longest path from the
root to a leaf. A tree may contain many *levels*, which are determined by the
length of every subsets of the longest path that determines the depth.

## Hypercubes

Hypercubes are a case of graphs that can be used to achieve strong connectivity without an exhaustive number of edges. The number of vertices in an hypercube is \(2^{n}\). The number of edges in an n-dimension hypercube is \(n2^{n-1}\).

A line is a 1-dimension hypercube, a square of a 2-dimension hypercube, and a cube is a 3-dimension hypercube. Notice that in any hypercube, the vertices have \(n\) number of neighbors where \(n\) equals the dimension of the hypercube.

In the case of a 3-dimension hypercube, there are 8 vertices where each has 3 neighbors, so the graph has a total of 12 edges. A complete graph of the same number of vertices would require 28 edges.

## References

- https://en.wikipedia.org/wiki/Graph_theory
- http://www.eecs70.org/static/notes/n5.html