Skip to main content
added 688 characters in body
Source Link
1001
  • 981
  • 3
  • 7

Consider the chromatic polynomial as a sum of monomials: $$P(G, k) = (k - r_1)(k - r_2)\cdots(k - r_n) = k^n + a_1k^{n-1} + \cdots + a_{n-1}k + a_n$$ It has been shown that $a_2 = \binom{e(G)}{2} - c_3(G)$, where $c_3(G)$ is the number of triangles in $G$.

For bipartite (and triangle-free graphs in general), we have $a_2 = \binom{e(G)}{2}$. It follows that \begin{align}\sum_{i=1}^n r_i^2 &= (-r_1-r_2-\cdots -r_n)^2 - 2(r_1r_2 + r_1r_3 + \cdots +r_{n-1}r_n)\\ &= a_1^2 - 2a_2\\ &= e(G)^2 - 2 \binom{e(G)}{2}\\ &= e(G)\end{align}


To prove that $a_2 = \binom{e(G)}{2} - c_3(G)$, you could use induction. As a base case, observe that the identity holds for empty graphs. For the induction step, recall that $$P(G, k) = P(G - uv, k) - P(G / uv, k)$$ and express the relevant coefficients of the two smaller graphs assuming the induction hypothesis:

  • The third coefficient of $P(G - uv, k)$ is $$\binom{e(G - uv)}{2} - c_3(G - uv) = \binom{e(G) - 1}{2} - (c_3(G) - |N(u) \cap N(v)|).$$

  • The second coefficient of $P(G / uv, k)$ (note that this polynomial has degree one smaller) is $$-e(G / uv) = - e(G) + |N(u) \cap N(v)|.$$ (Here you need $a_2 = - e(G)$, but that can again be proven by induction.)

Consider the chromatic polynomial as a sum of monomials: $$P(G, k) = (k - r_1)(k - r_2)\cdots(k - r_n) = k^n + a_1k^{n-1} + \cdots + a_{n-1}k + a_n$$ It has been shown that $a_2 = \binom{e(G)}{2} - c_3(G)$, where $c_3(G)$ is the number of triangles in $G$.

For bipartite (and triangle-free graphs in general), we have $a_2 = \binom{e(G)}{2}$. It follows that \begin{align}\sum_{i=1}^n r_i^2 &= (-r_1-r_2-\cdots -r_n)^2 - 2(r_1r_2 + r_1r_3 + \cdots +r_{n-1}r_n)\\ &= a_1^2 - 2a_2\\ &= e(G)^2 - 2 \binom{e(G)}{2}\\ &= e(G)\end{align}

Consider the chromatic polynomial as a sum of monomials: $$P(G, k) = (k - r_1)(k - r_2)\cdots(k - r_n) = k^n + a_1k^{n-1} + \cdots + a_{n-1}k + a_n$$ It has been shown that $a_2 = \binom{e(G)}{2} - c_3(G)$, where $c_3(G)$ is the number of triangles in $G$.

For bipartite (and triangle-free graphs in general), we have $a_2 = \binom{e(G)}{2}$. It follows that \begin{align}\sum_{i=1}^n r_i^2 &= (-r_1-r_2-\cdots -r_n)^2 - 2(r_1r_2 + r_1r_3 + \cdots +r_{n-1}r_n)\\ &= a_1^2 - 2a_2\\ &= e(G)^2 - 2 \binom{e(G)}{2}\\ &= e(G)\end{align}


To prove that $a_2 = \binom{e(G)}{2} - c_3(G)$, you could use induction. As a base case, observe that the identity holds for empty graphs. For the induction step, recall that $$P(G, k) = P(G - uv, k) - P(G / uv, k)$$ and express the relevant coefficients of the two smaller graphs assuming the induction hypothesis:

  • The third coefficient of $P(G - uv, k)$ is $$\binom{e(G - uv)}{2} - c_3(G - uv) = \binom{e(G) - 1}{2} - (c_3(G) - |N(u) \cap N(v)|).$$

  • The second coefficient of $P(G / uv, k)$ (note that this polynomial has degree one smaller) is $$-e(G / uv) = - e(G) + |N(u) \cap N(v)|.$$ (Here you need $a_2 = - e(G)$, but that can again be proven by induction.)

Source Link
1001
  • 981
  • 3
  • 7

Consider the chromatic polynomial as a sum of monomials: $$P(G, k) = (k - r_1)(k - r_2)\cdots(k - r_n) = k^n + a_1k^{n-1} + \cdots + a_{n-1}k + a_n$$ It has been shown that $a_2 = \binom{e(G)}{2} - c_3(G)$, where $c_3(G)$ is the number of triangles in $G$.

For bipartite (and triangle-free graphs in general), we have $a_2 = \binom{e(G)}{2}$. It follows that \begin{align}\sum_{i=1}^n r_i^2 &= (-r_1-r_2-\cdots -r_n)^2 - 2(r_1r_2 + r_1r_3 + \cdots +r_{n-1}r_n)\\ &= a_1^2 - 2a_2\\ &= e(G)^2 - 2 \binom{e(G)}{2}\\ &= e(G)\end{align}