#### Discover more from Algorithmically Speaking

# 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**.

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:

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.

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!