Functional Graphs and Permutation Graphs
=============================================

Definition 3.7.1 (Permutation Graph)
------------------------------
Consider a permutation
:math:`P: p_{1}, p_{2}, p_{3}, ..., p_{n}`
of the numbers 1 to n.

Consider an
:math:`n`-vertex
graph
:math:`G`
whose vertices are numbered from 1 to n.

For each
:math:`1 \le i \le n`,
we draw a directed edge from
:math:`i`
to
:math:`p_{i}`. This graph is called a permutation graph, constructed from the permutation
:math:`P`.

For example, consider the permutation
:math:`P: 2, 3, 1, 5, 4, 6`. The graph below is a permutation graph for this permutation:

.. figure:: /_static/dot/Permutation_Graph.svg
   :width: 80%
   :align: center
   :alt: If the user's internet is bad, this shows up

Theorem 3.7.2
------------------------------
**Statement:** The vertices of a permutation graph are partitioned into a set of cycles.

**Proof:** For every vertex in a permutation graph, its in-degree and out-degree are exactly one. We know that a directed graph in which the in-degree and out-degree of every vertex are equal to one is partitioned into a set of cycles (why?!)!

Theorem 3.7.3
------------------------------
**Statement:** If two elements in a permutation are swapped, then the number of cycles in its permutation graph changes by exactly one.

**Proof:** The proof of this theorem is left as an exercise for the reader.