# Graph degree as solution for undirected graph paint

Posted on

Problem

The problem is:

Given an undirected graph represented as an adjacency matrix and an
integer k, write a function to determine whether each vertex in the
graph can be coloured such that no two adjacent vertices share the same
colour using at most k colours.
Source: https://www.dailycodingproblem.com/

The proposed solution uses a backtracking algorithm (https://www.dailycodingproblem.com/blog/graph-coloring), but I would like to know if just evaluating the vertice degree is enough (source: https://youtu.be/LUDNz2bIjWI?t=169).

``````    boolean canBeColored(int[][] adjacencyMatrix, int colors) {

for (int row = 0; row < adjacencyMatrix.length; row++) {
int degree = 0;
for (int column = 0; column < adjacencyMatrix[row].length; column++) {
if (adjacencyMatrix[row][column] == 1) {
degree++;
}
}

if (degree > colors) {
return false;
}
}

return true;
}
``````

Solution

It is not. Consider a triangle graph which has tree nodes and three edges. All vertices has degree two but three colors are required to color it. Your function would fail for that input.

In fact, the problem is NP-complete meaning that it is not known if an efficient algorithm can be constructed for solving it. So if you can do it, you’ll win fame and fortune and also a very large monetary prize.