Intro to Graph Theory
Graph theory is the study of structures that have pairwise relations.
A graph consists of vertices, sometimes called nodes or points, that are connected by edges, which are sometimes referred to as lines or links. Typically edges are easiest to define as a set of the 2 vertices they connect.
Definition: A graph G=(V,E) is a set of vertices V and edges E that are made up of pairs of vertices.
In the graph below, the vertices are V={A, B, C, D}, and the edges are written as the pairs E={(A, B), (D, A), (D, C), (C, B)}.
An important note is that the above graph is a directed graph. We can tell it is a directed graph because the edges have arrows on them, indicating movement from one vertex, at the tail of the arrow, to the vertex at the head of the arrow. This means that the edges, which are written as pairs of vertices, must have a specific order to them. In the case above, the starting vertex is always written first, so (D, A) is an edge in the graph, but (A, D) is not.
When the edges are just lines with no arrows, the graph is undirected, which means the edges can be written in any order.
Types of Graphs
The above definition of a graph as well as ideas of directed versus undirected graphs are enough to start learning graph theory, but in this section I go over a few special cases and types of graphs.
Complete Graph
A complete graph is a graph where every node is connected to every other node. In the figure below, there are 12 nodes, each of which has an edge connecting it to every other vertex. In a complete graph with n vertices, which is denoted Kₙ, there are exactly n choose 2 edges. Typically a complete graph is undirected.
Complete graphs arise in a number of settings and often are useful in understanding more complex problems in graph theory. Understanding where a complete graph can be found gives insight into how connected a graph is.
Bipartite Graph
A bipartite graph has 2 sets of vertices. When the 2 sets are of size m and n, the complete bipartite graph is denoted kₙ,ₘ.
In the figure below, these sets are shown as yellow and blue. A graph is bipartite if there exist no 2 vertices in the same set that are joined in an edge. A graph is a complete bipartite graph if every vertex in one set is connected by an edge to every vertex in the opposite set, as is the case in the figure below.
Bipartite graphs are useful for thinking about matching problems. You can think of each of the 2 sets as a group that is to be matched with the opposite group. A classic example is using bipartite graphs to model who is interested in dating who, where people only data others from the opposite group.
Planar Graphs
A planar graph is any graph that you can draw on a flat piece of paper without crossing 2 edges over each other. While this doesn’t seem like the most complicated problem, identifying when a graph is planar or can be drawn in a planar form is an interesting problem.
On the left this graph doesn’t appear planar because 2 edges cross. In the middle graph, the diagonal edge has been moved to go “around the graph” so that no 2 edges cross, making it planar. Finally, the graph all the way on the right has some of the vertices shifted so that it looks a little cleaner.
It is not immediately apparent that the graphs on the left and right have the same structure of vertices and edges, but following the shift from the left to the right can help. This problem of identifying which graphs have similar structure, which graphs are isomorphic, is a fundamental problem in graph theory and is in the computational class of NP problems.
While it isn’t always easy to identify which graphs are similar, identifying which graphs are planar is reasonably well understood with the following theorem.
Wagner’s Theorem: A graph G is planar if and only if the complete graph K₅ or the complete bipartite graph K₃,₃ can’t be obtained from G by deleting edges or vertices or contracting edges.
Contracting vertices is what happens when an edge is deleted and the 2 nodes at the end of the edge are joined. I won’t give a proof of Wagner’s Theorem here, but it is a very powerful idea and important to understand.
This is only the tip of the iceberg for graph theory. There are a lot of great applications, ideas, and problems to think about. Graph coloring, disease transmission in a network, and the internet are all fundamentally based on the ideas behind graph theory.
If you made it this far, hit the clap button. I’m new to Medium, and trying to crank out some content about how I think about math, data science, and computers. Follow me that’s if your sort of thing.
