For an undirected graph $G=(V,E)$, the Vertex Coloring Problem is assigning a color to each vertex, such that colors on adjacent vertices are different and the number of colors used is minimized. One model for this problem is:
If we directly assign each vertex a color (i.e. define an integer variable $ x_i \forall i \in [1,|V|]$ then we need to ensure that adjacent neighbors are assigned different integers (i.e. $ x_i\neq x_j \forall i\neq j$ such that $i$ is neoghbor of $j$ ). We can linearize these constraints by defining another binary variables $\delta_{i,j}$, and the final model is:
\begin{array}{rlc}{\textstyle\text{minimize}}\hspace{1em}&z& \\[3pt]{\textstyle\text{subject to}}\hspace{1em}&x_i-x_j \ge 1-|V|\delta_{i,j} \hspace{1em}&\forall i,j \in E\\[3pt]& x_i-x_j \le -1+|V| (1-\delta_{i,j}) \hspace{1em}&\forall i,j \in E\\[3pt]& z\ge x_i \hspace{1em}&\forall i\in V \\[3pt]& x_i\in \{1,...,|V|\}\hspace{1em}&\forall i\in V \\[3pt]& \delta_{i,j} \in \{0,1\}\hspace{1em}&\forall i,j\in E \\[3pt]& z\ge0 \end{array}
Can we avoid using variable $z$ and constraints $z\ge x_i \ \ \forall i$? Is it correct If we define the objective function like the following.
\begin{array}{rlc}{\textstyle\text{minimize}}\hspace{1em}&\sum_{i=1}^{|V|}x_i& \\[3pt]{\textstyle\text{subject to}}\hspace{1em}&x_i-x_j \ge 1-|V|\delta_{i,j} \hspace{1em}&\forall i,j \in E\\[3pt]& x_i-x_j \le -1+|V| (1-\delta_{i,j}) \hspace{1em}&\forall i,j \in E\\[3pt]& x_i\in \{1,...,|V|\}\hspace{1em}&\forall i\in V \\[3pt]& \delta_{i,j} \in \{0,1\}\hspace{1em}&\forall i,j\in E \end{array}
How can I prove or reject the equality of these two formulation?
This does not solve the vertex coloring problem. Consider the tree consisting of an edge $ab$, a lot of vertices $x_i$ connected to $a$ and a lot of vertices $y_i$ connected to $b$. Then the sum-minimizing formulation will choose to color all of $x_i$ and $y_i$ with color $1$ and $a,b$ with colors $2,3$.