# Graph degree as solution for undirected graph paint

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++) {
degree++;
}
}

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

return true;
}

• What programming language is this? Where is the rest of the program? Commented Dec 26, 2019 at 14:32
• It is Java, and this is the whole program. Commented Dec 26, 2019 at 14:41