Recursion not going back looking for different path

I am trying to write a backtracking algorithm for harmonious graph coloring (no adjacent colors can be the same, and also each pair of colors can appear only once). This is the backtracking function:

void Graph::colorBacktrack(int a, int b) {

print();
for (int i = 1; i <= colors; i++) //assigning colors until match
{
    elems[a][b] = i; //color
    if (check(a, b)) break; //if it's alright break
    if (i == colors) // if all the colors have been used - 
        return;      //return one stack back and look again

}

int nextA;
int nextB = b;
if (a < size - 1 ) nextA = a + 1;
else {
    nextA = 0;
    nextB = b + 1;
}

if (a == size && b == size - 1) //when array is complete - cout finished
{
    cout << endl << endl << "Finished" << endl << endl;
}

colorBacktrack(nextA, nextB); //go to next node when everything is fine

}

checking is working properly and all the other things. The problem is that the output is wrong - at the end it shows something like this:

1 4 2 6

2 5 7 8

3 6 4 8 <--- this is wrong

1 7 3 0 <--- this is also wrong

So when it cannot find a solution in current tree it just ends everything instead of going up. Why is it happening?