Graph Theory Fundamentals

In my previous post (can be found here), we discussed the importance of Graph Theory and how we find it everywhere in the world. In this post, we will explore the fundamental definitions along with examples to cement a foundational understanding of Graph Theory to aid in future posts going further in this study.

The structure and many of the definitions have been adapted from the lecture notes of Nathan Marianovsky’s Graph Theory course at UC Santa Cruz.

The Basics

Let’s first go over the primal definition of a graph.

Definition 1: A graph G is a pair G = (V, E) where V is the vertex set and E is the edge set where V is non-empty and E \subseteq \{\{u, v\} : u, v \in V\}.

I believe its best to understand this definition through an example. Consider the following graph G.

Rendered by QuickLaTeX.com

Then we have our vertex set V = \{a, b, c, d\} as seen in the image, and we represent each edge as a set of two vertices, so our edge set is E = \{\{a, b\}, \{a, c\}, \{b, d\}, \{c, d\}\}. The reason we represent edges as a set is that the order of the vertices in an undirected edge does not matter; later with directed edges (edges with arrows), we account for the order.

Furthermore, we write an edge \{u, v\} as uv for simplicity. Also when talking about different graphs, we tend to write the vertex and edge sets as V(G) and E(G), respectively, in order to limit confusion.

Now let’s talk about adjacency and incidence of vertices and edges and also the concept of neighbors and neighborhoods.

Definition 2: For a graph G, every two vertices u, v \in V(G) are adjacent if the edge uv \in E(G).

Definition 3: For a graph G, the vertex u \in V(G) is incident to every edge uv \in E(G), and vice versa.

Definition 4: For a graph G, every two edges uv, vw \in E(G) are edge adjacent where u, v, w \in V(G).

Definition 5: For a graph G, if uv \in E(G) for u, v \in V(G), then we call u and v neighbors, and the neighborhood of u, denoted by N(u), is the set of all neighbors of u.

These are some of the basic terminologies that we use in Graph Theory so it was important to introduce them first up. If we take the example from before, the vertices a and b are adjacent, a is incident to the edge ab, ab and ac are edge adjacent, and the neighborhood of a comprises of b and c.

A metric that is extremely important in the study of Graph Theory is the degree of a vertex defined below.

Definition 6: For a graph G, the degree of any vertex v, denoted by \text{deg}(v), is the number of vertices adjacent to v, i.e. \text{deg}(v) = |N(v)|.

When the graph in discussion may be ambiguous, we denote the degree by \text{deg}_G(v), and this notion falls under basic Graph Theory notation. Furthermore, as an example, the degree of an entity or vertex of a social network shows the popularity of that entity since the more adjacent vertices or the bigger its neighborhood, the more that entity is connected with many other entities in the social network.

Now we shall define the subgraph which is essentially referring to graphs “contained” in the supergraph (or parent graph).

Definition 7: For two graphs G and H, if V(H) \subseteq V(G) and E(H) \subseteq E(G), then H is a subgraph of G, denoted by H \subseteq G.

For example consider the graph G again.

Rendered by QuickLaTeX.com

Now the following graph H_1 is a subgraph of G, i.e. H_1 \subseteq G.

Rendered by QuickLaTeX.com

Notice that we are missing an edge from G in H_1. Meanwhile, the following graph H_2 is also a subgraph of G, i.e. H_2 \subseteq G.

Rendered by QuickLaTeX.com

Notice that instead of missing just an edge, we are missing a vertex from G in H_2. Lastly, even G is a subgraph of G.

We call a subgraph a proper subgraph if we are missing at least a vertex or edge, or, in other words, the subgraph isn’t the original graph itself. So in the last example, both H_1 and H_2 are proper subgraphs of G, but G is not a proper subgraph of G.

The subgraphs of a graph can tell us a lot about the graph itself, and this is explicitly seen in graph card decks, which we may discuss in the future. Also, the subgraph count can convey conclusions of the graph structure; for example, social networks tend to have a lot of triangle-shaped subgraphs.

This completes a basic introduction to the graph and some terminology. We haven’t discussed other types of graphs yet, but in later posts, we will go over the multigraph, pseudograph, and digraph which have different structures than the graph definition presented here which refers to the undirected graph.

Graph Traversal

The key to Graph Theory in the algorithmic sense is to understand graph traversal. By traversal, we mean to traverse edges to get from vertex to vertex. You might have heard of the Shortest Path Problem where we try to find the shortest connection between two vertices in a graph, or the Max-Flow Problem (some preliminary information can be found here) which indirectly uses traversals to determine a solution; these classes of problems all depend on traversing the graph in order to reach their conclusions. Although we won’t go into these algorithms, we will give a brief introduction to traversal.

Let’s dive into the definitions. We will be using basing all our examples from the following graph G.

Rendered by QuickLaTeX.com

The first most basic method of traversal is called the walk as defined below.

Definition 8: For graph G, a uv walk is a sequence of vertices starting with u and ending with v where consecutive vertices constitute edges in G, i.e. w = (v_0, \ldots, v_k) where v_0 = u and v_k = v and \{v_i, v_{i+1}\} \in E(G) for all i = 0, \ldots, k - 1 is a uv walk.

This can be best seen through examples. Taking our graph G from above, consider the walk going from a to f where we go up to b, then c, then e, and then back to b, and back to c, and then back to e, and then d, and then f. We can write this af walk as w = (a, b, c, e, b, c, e, d, f). Notice that we visited b, c, and e twice and even went through the same edges twice. As the name suggests, a walk is really like a walk on the graph with absolutely no conditions.

Next with a few more restrictions on the structure of the traversal, we define the trail as follows.

Definition 9: For graph G, a uv trail is a walk where no edge is traversed twice.

In our last example of a walk, note that we repeated the edge bc, ce, and eb twice, so w was not a trail. However, instead of going to c after going back to b from e, if we rather go to d and then f, we get the trail t = (a, b, c, e, b, d, f), and we see that no edge is traversed more than once as required.

Then with further structure, we define the path, which I believe is the most important mode of traversal, again in the algorithmic sense.

Definition 10: For a graph G, a uv path is a trail where no vertex is traversed twice.

Obviously w was not a path since it wasn’t even a trail, and even t is not a path since we visit vertex b twice. However, p = (a, b, c, e, d, f) is a valid path since we don’t traverse any edge or vertex more than once. Something interesting to note is that by not traversing vertices twice, we necessarily cannot have traversed any edge more than once, so a path can be defined as a walk with no vertex traversed twice.

Paths mean a lot in graph theory and algorithms as they are the most structured mode of traversal with least “overhead,” i.e. we never repeat any edge or vertex. Many times, we wish to optimize our mode of traversal, and so by repeating vertices and edges we are unnecessarily lengthening the traversal, so we look for paths from the start and destination.

Before continuing, let’s briefly define traversal length: which for some traversal (a walk, trail, or path) s = (v_0, \ldots, v_k) has length k, i.e. we traverse k edges.

Now let’s talk about closed traversals, i.e. we start and end at the same vertex. First we have the circuit.

Definition 11: A closed trail of length at least 3 is called a circuit, i.e. a circuit c = (v_0, \ldots, v_k) is a trail where v_0 = v_k and k \ge 3.

For example, consider the circuit c = (a, b, d, e, b, c, a) where we clearly don’t repeat any edge traversals and with length at least 3, and we start and end with the same vertex a.

Again with further restrictions, we define the cycle which is the most common version of closed traversal similar to the paths.

Definition 12: A closed path of length at least 3 is called a cycle, i.e. a cycle c = (v_0, \ldots, v_k) is a path where v_0 = v_k and k \ge 3.

For example, consider the cycle c = (a, b, d, e, c, a) where we don’t repeat any vertices other than the first and last vertex (since its closed) and length is at least 3. Another way to define the cycle is to call it a circuit with no repeated vertices other than the first and last vertex in the sequence.

There are multiple algorithms that will be discussed in the future employing all these modes of graph traversal. Further, both the path and cycle fall under special graph families which will be discussed in the future. Nevertheless, knowing these basic traversal definitions is imperative in further study of Graph Theory.

Graph Connectedness

Now that we have talked about traversal, it makes sense why we would like to know if a traversal is even possible. We call this the reachability problem: to determine if we can we reach vertex v from vertex u in a graph. Before we go into the formal definition, let’s prove a key theorem first. It will additionally give you an initial taste of the Graph Theory proof dynamic which tends to be slightly more nuanced and semantic in its style.

Theorem 1: If there exists a uv walk in graph G, then there exists a uv path in G.

Proof: Consider some uv walk in G, call it to w = (v_0, \ldots, v_k) with v_0 = u and v_k = v and for some k \ge 0. If k = 0, then u = v, so clearly there exists a uu path. So assume k > 0. If w is a path, i.e. we repeat no vertices, then we are done.

So further assume that w is not a path, i.e. w repeats some vertex, so we know there exists some v_i = v_j with i < j, without loss of generality. Notice that the sub-walk of c = (v_i, \ldots, v_j) is actually a closed-walk, so if we remove the extra vertices it won’t affect our traversal. So now consider the walk w' = (v_0, \ldots, v_i, v_{j + 1}, \ldots, v_k) which is also a uv walk, but now we have lost at least one repeated vertex. We continue this procedure on w' till we reach a walk with no repeated vertices, call it p, which is our desired uv path. \quad \blacksquare

To emphasize the principle utilized in the above proof, consider some walk w which we depict below.

Rendered by QuickLaTeX.com

Due to the closed sub-walk from v_i to v_j (which are the same vertex), we can simply get rid of them to get the following walk.

Rendered by QuickLaTeX.com

We essentially are repeating this process till of course there are no repeated vertices, and at that point, we have derived a uv path as required.

Now we define reachability as follows which should be obvious after our last theorem.

Definition 13: For a graph G, vertex v is reachable from u if there exists a uv path in G.

Since the most primitive and abstract mode of traversal is a walk, and by Theorem 1, we have shown that the existence of a walk implies a path, the above definition makes sense and is valid. Moreover, both Theorem 1 and Definition 13 stand testament to the importance of paths in Graph Theory.

Now, this leads into the important yet simple concept of connectedness which indicates whether a graph is connected or disconnected. We introduce this concept formally as follows.

Definition 14: A graph G is connected if for every pair of vertices are reachable from each other; otherwise G is disconnected.

A graph is connected if we can traverse to any other vertex from any vertex, and, on the other hand, a graph is disconnected if we cannot get from one vertex to another. As we will see now, the definition overcomplicates this notion which is quite clear in small examples, and it’s best to familiarize these key concepts through examples. Consider the following graph H_1.

Rendered by QuickLaTeX.com

Now consider another graph H_2 depicted below.

Rendered by QuickLaTeX.com

We see that H_1 is connected because there is a path between every pair of vertices. However, H_2 is disconnected clearly just by seeing the two parts of the graph with no edges in between.

This concept of connectedness is deemed important in examples like network systems where if there is no line (path) connecting one system (vertex) to another, we have a problem if the network system is not connected.

The connectedness graph says quite a lot about the graph, but in the disconnected case we see that we can break down the graph into connected components as we saw the two components in the above disconnected graph. Essentially the connected components are the maximal connected subgraphs defined formally below.

Definition 15: A connected component is a connected subgraph of a graph G such that it is not a subgraph of any other connected subgraph. Further, the number of connected components of G is denoted by k(G).

Also, many times we label connected components as just components when the context is clear. Further, the notion of not being a subgraph of any other connected subgraph provides for the maximal property of connected components. Although the definition makes it quite clear, consider the following disconnected graph G.

Rendered by QuickLaTeX.com

The first component of G is depicted below.

Rendered by QuickLaTeX.com

The second component of G is depicted below.

Rendered by QuickLaTeX.com

And lastly the third component is shown below.

Rendered by QuickLaTeX.com

It’s clear to see why the above subgraphs are connected components of G, and since we count three of them, we know k(G) = 3 in this example.

Moreover, the connected component count k(G) plays a crucial role in many applications like a power grid setting where we wish to know how many separate power grid systems in place in that state. If we consider every power line as an edge, and tower as a vertex, by determining the number of connected components in this graph we find the desired system count. This example emphasizes the importance of just the count of connected components along with the components themselves.

Before we continue, I wish to share another way to conceptualize the connected component. If we consider reachability as an equivalence relation, the equivalence classes of the graph are the connected components. This stems from the definition of connected graphs with regards to total reachability. It’s a cleaner way to think about connected components, but I refrain from keeping it as the formal definition due to the extra overhead of including relations.

Now that we have understood that graphs are in either a connected or disconnected state, many times theorems will apply to only connected graphs, so in the disconnected case we simply apply the theorem to the components. Also, if a graph as one component its anyway connected, so this thinking can be applied to all graphs and is a nice thing to keep in the back of your mind.

Just knowing a graph is connected implies a lot, but at the same time, there are so many possibilities. Thus we introduce the concept of connectivity which looks into how connected a graph is. The metric of vertex-connectivity is the least number of vertices required to remove from the graph to disconnect it, and similarly, we define edge-connectivity. In this way, we clearly have devised a way to express how connected a connected graph is, and this is important when we wish to determine the vulnerability of a system. For example in a chip, we wish for a high edge-connectivity so that if one wire malfunctions the entire system isn’t affected. The details of connectivity will be discussed in an upcoming post with formal definitions and comprehensive examples.

Looking Forward

Throughout this post, I have been mentioning topics that will follow this post to go deeper into the subject, so I’ll be posting accordingly. Something that wasn’t mentioned here was the crucial theory of trees which will be discussed in an upcoming post. Furthermore, I will be writing on some more advanced Graph Theory topics simultaneously, primarily focusing on my interests in the subject which tend to be more algorithm-based. The theory presented here is fairly sufficient to start going into graph algorithms on which I will tend to write about frequently as well. So keep on the lookout for upcoming posts in Graph Theory and Graph Algorithms!

About the Author

Leave a Reply

Your email address will not be published. Required fields are marked *

Related Posts