Algorithmically Speaking - #4: Neighbors, Degrees, and Colorings

This is the summary version of the article published in the Algorithmically Speaking newsletter which is only dedicated to exploring some of the most beautiful algorithmic problems and solutions in the history of Computer Science.

You can read the complete version by clicking on this link.

---

Hello there!

Today we will be diving into one of the most common ways of representing data and modeling problems (and solutions) in Computer Science. We will be talking about Graphs.

This is the second of a series of posts introducing graph theory in a very visual way.

It will consist of some basic definitions of graph theory that will lay the basis for us to be able to explore more complex topics in future posts. The idea is to present the definitions along with visual representations, to help in the process of learning new concepts.

Take a look at the previous posts of this series if you think you need some more background before diving into the content that will be exposed in this article:

1. Algorithmically Speaking - #3: Nodes, Edges, and Connectivity

At the end of the post, you will find some algorithmic challenges so you can try and apply the topics that I will explain today. Feel free to skip to that part if you think you already have the necessary skills to solve them.

Let’s begin!

---

Neighbors and Degrees

Two nodes are neighbors or adjacent if there is an edge between them. The degree of a node is the number of its neighbors.

In the following graph, we have highlighted a node (colored in green), its neighbors (colored in red), and the edges between them (colored in blue):

We can see that the green node has three incident edges and three neighbors, and therefore, it has a degree equal to 3.

In the next image, we can see the degree of every node:

Something to notice is the fact that the sum of degrees in a graph is always 2m, where m is the number of edges. This happens because each edge increases the degree of exactly two nodes by one. So, the sum of the degrees is always even.

A graph is regular if the degree of every node is a constant d. A graph is complete if the degree of every node is n−1, where n is the number of nodes in the graph. That is, the graph contains all possible edges between the nodes. By definition, a complete graph is a regular graph.

Here’s an example of a regular graph that is not complete. Notice how the degree of every node is 2:

And this is an example of a complete graph. Notice how the degree of every node is 3 and there are 4 nodes:

When we are referring to directed graphs, we define the indegree of a node as the number of edges that end at the node, and the outdegree of a node as the number of edges that start at the node.

Here’s an example highlighting a node with an indegree equal to 2 and an outdegree equal to 1:

And these are the values of indegree/outdegree for every node. Notice how some nodes can have indegree or outdegree equal to 0:

Colorings

In a coloring of a graph, each node is assigned a color so that no adjacent nodes have the same color.

A graph is called bipartite if it is possible to find a coloring of its nodes using two colors. It can be proven that a graph is bipartite exactly when it does not contain a cycle with an odd number of edges.

For example, the following graph is bipartite:

We can claim that it is bipartite because we can find a coloring of the graph using only two colors:

And here’s a more intuitive way to visualize bipartite graphs. The previous and the following graphs are the same:

With this representation, it becomes visually more clear that the nodes can be split into two sets, and that every edge in the graph connects nodes from different sets.

Now, let’s take a look at the following graph:

No matter how hard you try, you won’t be able to find a coloring of this graph using only two colors. Remember earlier, when we said that cycles of odd length and bipartiteness are related?

Inspecting the graph closely, we can notice that it contains a cycle of length 3. It won’t be possible to color this cycle (or the entire graph) using only two colors:

In future posts, we will explore algorithms to determine if a graph is bipartite or not. Also, we will dig deeper into how the degrees of nodes play an important role in finding topological orderings in directed graphs.

Conclusions

I hope I was able to ignite your passion for Graph theory by driving you through some of the basic definitions that will allow us to build the foundations for learning more complex concepts and applications of graphs.

Some takeaways:

• Two nodes are neighbors or adjacent if there is an edge between them. The degree of a node is the number of its neighbors.

• A graph is regular if the degree of every node is a constant d. A graph is complete if the degree of every node is n−1, where n is the number of nodes in the graph.

• When we are referring to directed graphs, we define the indegree of a node as the number of edges that end at the node, and the outdegree of a node as the number of edges that start at the node.

• A graph is called bipartite if it is possible to find a coloring of its nodes using two colors. It can be proven that a graph is bipartite exactly when it does not contain a cycle with an odd number of edges.

I wish you good luck when solving this week’s challenges. Don’t forget to share your progress with the community!

And if you think this post can be helpful for someone, share it with them. Nothing will make me happier!

See you next week!

---

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn