# 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.

Given a set of vertices $V$, the set of all possible connections is denoted as $\frac{V}{2} = \{ \{ x, y \} \mid x \in V \land y \in V \land x \neq y \}$. Notce that given edges $E$, is must hold that $E \subseteq \frac{V}{2}$.

### Degree

The degree of a vertex is the number of edges incident to such vertex. Formally, $degree(u) = |\{ v \in V \mid \{ 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.

The degree if a vertex, denoted $deg(v)$, is the cardinality of its neighborhood. Notice that given a graph with vertices $V$ and $m$ number of edges, then $2m = \sum_{v \in V} deg(v)$.

## Incidence (Neighborhoods)

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. Formally,
given edges
$E$
and vertices
$A, B \in V$,
the neighborhood of
$A$
is
$N(A) = \{ x \in V \mid (A, v) \in E \}$.

## 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 $\langle\{ B, A \}, \{ A, C \}\rangle$.

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.

### 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 graph is a tree if it contains no cycles. 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