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

A visual introduction to the concepts of degrees, colorings, and bipartite graphs.

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.

Degrees and colorings in graphs, isometric - app.leonardo.ai

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):

A node with its incident edges and neighbors.

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:

A graph showing 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:

A regular graph of degree 2.

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

A complete graph with 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:

Example of a node, incoming and outgoing edges, and its relation to indegree and outdegree.

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

A directed graph showing the indegree and outdegree for every node.

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:

A bipartite graph.

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

A valid coloring of a bipartite graph.

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

A common way for representing bipartite graphs. The two sets are more clearly visible.

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:

A non-bipartite 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:

A cycle of odd length, which cannot be colored using 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.

In the meantime, it’s time to try what you’ve learned!

Test your Skills

Now that we know some basic definitions of graph theory, I will leave you with two challenges that you can think about during the week.

We can discuss the answers to these problems as a community and you can share your answers privately by replying to this email.

Here we go:

Problem #1: What is the minimum amount of colors needed in a valid coloring of a cycle with an odd length?

Problem #2: Is a tree a bipartite graph?

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!