"A graph with $n \ge 2$ vertices has at least two vertices with same degree". Is there a generalization of this fact?

63 Views Asked by At

Namely, I'm looking for something along the lines of

If $k = \chi(G)$, then there exists $k$ disjoint subsets of vertices $S_1, \dots, S_k$ such that $$ \sum_{v \in S_i} d(v) $$ is constant, for all $i$.

where, $d(v)$ is the degree of vertex $v$.

1

There are 1 best solutions below

0
On

Probably the simplest counter-example to your statement is $K_5-e$: the complete graph on $5$ vertices, with one edge deleted (or the skeleton graph of a triangular bipyramid).

enter image description here

(Image source: House of Graphs)

The chromatic number is $4$, but the vertex degrees are $3, 3, 4, 4, 4$, from which we cannot make more than $3$ subsets with equal sum.