I'm studying graph theory, coloring at the moment, for a computer science course. I'm stuck with a proof of the following exercise from an old exam:
A graph is $d$-numerable ($d \in \Bbb Z_{>0}$) if and only if all of its nodes have degree $d$ and it's possible to assign an integer between $1$ and $d$ to each node in a way such that for every node all of it's neighbours have different numbers assigned.
A $d$-numeration is such assignment. A graph is $d$-numerable if and only if it has associated a $d$-numeration. Example: $K_{2.2}$ is $2$-numerable and a possible $2$-numeration is the following:
Show that if $G$ is $d$-numerated then for each integer between 1 and $d$ there exists at least $2$ adjacent nodes that have assigned that integer, and there exactly $n/d$ nodes that have assigned that integer.
For the first part, showing that there are at least 2 adjacent nodes sharing each integer, I thought of the following by contradiction:
Say it is not true, no two nodes share assignment. Then you show that as a node $v$ has an integer assigned to it and $d$ neighbours, each one of them must have different integers assigned -and different form $v$-. But you have $d$ neighbours and only $d-1$ possible integers -because of $v$-, then it can't be $d$-numerable.
I don't know what to say about the other part, that there are exactly $n/d$ numbers for each assigned integer. After a while I realized that the complement of such graph is a proper d-coloring. But I don't know if that helps me with this proof.
Any help will be appreciated, thank you!