Real-rooted flow polynomials have only integer roots

Abstract

In this article, we show that for any bridgeless graph $G$, if its flow polynomial $F(G,x)$ has real zeros only, then $G$ is the dual of a chordal plane graph and each zero of $F(G,x)$ is an integer in the set $\{1,2,3\}$.

1 Preliminaries

All graphs considered in this paper are finite and undirected, and may have loops and parallel edges. For any graph $G$, let $V(G)$ and $E(G)$ be the vertex set and edge set of $G$, respectively.

In 1912, Birkhoff introduced the chromatic polynomial as a tool to attack the Four-Color Conjecture [1] . For any graph $G$, the chromatic polynomial $P(G,\lambda)$ of $G$ counts the number of proper $\lambda$-colorings of $G$ for each positive integer $\lambda$. Thus, the Four-Color Conjecture is equivalent to the assertion that $P(G,4)>0$ for all planar graphs $G$. It is then well known, from the deletion-contraction formula, that this counting function is in fact a polynomial in $\lambda$ with integer coefficients, hence the name. Over the years, the chromatic polynomial has become one of the fundamental graph polynomials and an important object of study, due to the close connections between its algebraic properties and the structural properties of the underlying graph. See [5, 7, 12, 13] for reference.

In particular, the roots of $P(G,\lambda)$ are called the chromatic roots of $G$. Clearly, $0$ is a chromatic root of every graph. Also, it can be easily verified that all chromatic roots of a chordal graph are nonnegative integers, where a graph is chordal if it contains no induced cycle of length greater than three. Meanwhile, there exist non-chordal graphs whose chromatic roots are all integers [11, 8, 7, 6, 2], as well as non-planar graphs whose chromatic roots are all real but are not all integers [4]. Motivated by these observations on integral and real chromatic roots, it is natural to consider the following question, which remains widely open.

Problem 1 ([3]).

Is there a planar graph $G$ that has real chromatic roots only and contains non-integral chromatic roots?

Clearly, for Problem 1, it suffices to consider non-chordal planar graphs.

On the other hand, the flow polynomial was introduced by Tutte [14] in 1950 as a natural counterpart of the chromatic polynomial. For any graph $G$, the flow polynomial $F(G,\lambda)$ of $G$ counts the number of nowhere-zero $\Gamma$-flows on any orientation $D$ of $G$, where $\Gamma$ is an additive Abelian group of order $\lambda$, for each positive integer $\lambda$. It is well known that $F(G,\lambda)$ is also a polynomial in $\lambda$ with integer coefficients, as can be seen directly from the following deletion-contraction formula [15]:

$$F(G,\lambda)=\left\{\begin{array}[]{@{}ll}1,&\text{if }E(G)=\varnothing,\\ 0,&\text{if }G\text{ has a bridge},\\ F(G_{1},\lambda)F(G_{2},\lambda),&\text{if }G=G_{1}\cup G_{2},\\ (\lambda-1)F(G-e,\lambda),&\text{if }e\text{ is a loop},\\ F(G/e,\lambda)-F(G-e,\lambda),&\text{if }e\text{ is neither a loop nor a bridge},\end{array}\right.$$

where $G/e$ and $G-e$ are the graphs obtained from $G$ by contracting $e$ and deleting $e$ respectively, and $G_{1}\cup G_{2}$ is the disjoint union of graphs $G_{1}$ and $G_{2}$.

In analogy with chromatic roots, the roots of $F(G,\lambda)$ are called the flow roots of $G$. For any connected plane graph $G$, a classical duality due to Tutte [14] shows that

$$P(G,\lambda)=\lambda F(G^{*},\lambda),$$

where $G^{*}$ is the dual plane graph of $G$. Thus, Problem 1 can be equivalently stated in terms of flow roots as follows.

Problem 2 ([4, 3]).

Is there a planar graph $G$ that has real flow roots only and contains non-integral flow roots?

Problem 2 also remains open. In fact, even the following weaker question is still unsolved.

Problem 3 ([4, 3]).

Is there a graph $G$ that has real flow roots only and contains non-integral flow roots?

Before introducing our main results, we first review some relevant developments concerning Problems 1, 2, and 3. Note that we restrict our attention to bridgeless graphs when considering flow polynomials as $F(G,\lambda)$ is trivially zero if $G$ has a bridge.

In 2011, Kung and Royle have characterized the graphs whose flow roots are all integers [10].

Theorem 4 ([10]).

If $G$ is a bridgeless graph, then its flow roots are integral if and only if $G$ is the dual of a chordal and plane graph.

Inspired by Theorem 4, it is natural to ask whether every graph whose flow roots are all real must also be the dual of a chordal plane graph [3]. Moreover, Dong extended Theorem 4 by determining all possible flow roots of graphs with only integral flow roots as follows [4].

Theorem 5 ([4]).

Let $G$ be a graph with real flow roots only. The following statements are equivalent:

1. $G$ is the dual of some chordal and plane graph;

2. each flow root of $G$ is in the set $\{1,2,3\}$;

3. $G$ has no flow roots in the interval $(1,2)$.

In this paper, building on the aforementioned results, we give negative answers to Problems 1, 2, and 3.

Theorem 6.

Let $G$ be a bridgeless graph. Then $G$ has only real flow roots if and only if $G$ has only integral flow roots if and only if $G$ is the dual of a chordal and plane graph. Moreover, every flow root of such a graph belongs to $\{1,2,3\}$.

The following corollary is then direct.

Corollary 7.

Let $G$ be a loopless planar graph. Then $G$ has only real chromatic roots if and only if $G$ has only integral chromatic roots if and only if $G$ is chordal. Moreover, every chromatic root of such a graph belongs to $\{0,1,2,3\}$.

We shall present some preliminary results in Section 2 and prove Theorem 6 in Section 3.

2 Preliminaries

In this section, we introduce some notations and properties of flow polynomials that will be used in the proof of Theorem 6.

Let $G$ be a graph. For any $V_{0}\subseteq V(G)$, let $G-V_{0}$ denote the graph obtained from $G$ by deleting all the vertices in $V_{0}$ and all the edges incident with some vertex in $V_{0}$. For any $E_{0}\subseteq E(G)$, let $G-E_{0}$ denote the spanning subgraph of $G$ with edge set $E(G)\setminus E_{0}$. Moreover, we simply write $G-v$ for $G-\{v\}$ and $G-e$ for $G-\{e\}$. Also, for any $u,v\in V(G)$, let $G+uv$ be the graph obtained from $G$ by adding an edge between $u$ and $v$. $G$ is said to be nonseparable if either $|E(G)|\leq|V(G)|=1$ or $G$ is connected without loops or cut-vertices, and separable otherwise. A block of $G$ is a maximal nonseparable subgraph of $G$. An edge-cut $S$ of $G$ is said to be proper if $G-S$ has no isolated vertices. $G$ is $k$-edge-connected if $G$ is connected with $|V(G)|\geq 2$ and every edge-cut of $G$ has size at least $k$.

The following lemma indicates that the flow polynomial $F(G,\lambda)$ of $G$ can be factorized or simplified whenever $G$ contains a loop, $G$ is disconnected, $G$ is separable, $G$ contains a 2-edge-cut, or $G$ contains a proper 3-edge-cut.

Lemma 8 ([9, 15]).

Let $G$ be a bridgeless graph.

1. If $G$ contains a loop $e$, then $F(G,\lambda)=(\lambda-1)F(G-e,\lambda).$

2. If $G$ is disconnected and $G_{1},G_{2},\dots,G_{k}$ are the components of $G$, then

   $$F(G,\lambda)=\prod_{i=1}^{k}F(G_{i},\lambda).$$

3. If $G$ is connected and $G_{1},G_{2},\dots,G_{k}$ are the blocks of $G$, then

   $$F(G,\lambda)=\prod_{i=1}^{k}F(G_{i},\lambda).$$

4. If $e$ is an edge in a 2-edge-cut of $G$, then $F(G,\lambda)=F(G/e,\lambda)$.

5. Assume that $G$ is bridgeless, $S$ is a proper 3-edge-cut of $G$ whose removal separates $G$ into two subgraphs $H_{1}$ and $H_{2}$. Let $G_{i}$ be the graph obtained from $G$ by contracting $E(H_{3-i})$ for $i=1,2$. Then

   $$F(G,\lambda)=\frac{F(G_{1},\lambda)F(G_{2},\lambda)}{(\lambda-1)(\lambda-2)}.$$

   An example is as shown in Figure 1.

Figure 1: $G$ has a 3-edge-cut

Moreover, some standard facts of flow polynomials are as follows.

Proposition 9 ([16, 10]).

Let $G$ be a bridgeless graph, where $|V(G)|=n$ and $|E(G)|=m$.

1. The polynomial $F(G,\lambda)$ has no real roots in $(-\infty,1)$.

2. If $m>0$ and $G$ is nonseparable, then $1$ is a flow root of $G$ with multiplicity one.

3. If $G$ is $3$-edge-connected, then

   $$F(G,\lambda)=\sum_{i=0}^{m-n+1}b_{i}\lambda^{i},$$ (2.1)

   where $b_{r}=1,b_{r-1}=-m$, and $b_{r-2},b_{r-3},\dots,b_{0}$ are integers.

Then we establish our key lemma below.

Lemma 10.

Let $G$ be a nonseparable $3$-edge-connected graph with $|V(G)|=n$ and $|E(G)|=m$. If $G$ has only real flow roots and $m\geq n+1$, then $m\leq 2n-1$. Moreover, if the equality holds, then $F(G,\lambda)=(\lambda-1)(\lambda-2)^{n-1}.$

Proof. Note that $G$ is nonempty as $m\geq n+1$ and $G$ is $3$-edge-connected. Let $r=m-n+1$. Then $r\geq 2$. By Proposition 9 (iii), we assume that

$$F(G,\lambda)=\sum_{i=0}^{r}b_{i}\lambda^{i},$$

where $b_{r}=1$, $b_{r-1}=-m$, and $b_{r-2},b_{r-3},\dots,b_{0}$ are integers.

Since $F(G,\lambda)$ is a polynomial of degree $r\geq 2$, let $\rho_{1},\rho_{2},\ldots,\rho_{r}$ be all the roots of $F(G,x)$, counted with multiplicity. Then by Proposition 9 (i) and (ii), we can further assume that $\rho_{1}=1$, and $\rho_{i}>1$ for $2\leq i\leq r$. Clearly, $\sum_{i=1}^{r}\rho_{i}=-b_{r-1}=m$, implying that

$$n-1=m-r=\sum_{i=1}^{r}\rho_{i}-r=\sum_{i=1}^{r}(\rho_{i}-1)=\sum_{i=2}^{r}(\rho_{i}-1).$$ (2.2)

Let $Q(\lambda)=\prod\limits_{i=2}^{r}(\lambda-\rho_{i})$. Then $Q(1)\neq 0$ and $F(G,\lambda)=(\lambda-1)Q(\lambda)$. Further,

$$\left\{\begin{aligned} &F^{\prime}(G,\lambda)=\sum_{i=1}^{r}ib_{i}\lambda^{i-1}.\\ &F^{\prime}(G,\lambda)=Q(\lambda)+(\lambda-1)Q^{\prime}(\lambda)=\prod_{i=2}^{r}(\lambda-\rho_{i})+(\lambda-1)Q^{\prime}(\lambda).\\ \end{aligned}\right.$$

Then it is clear that $F^{\prime}(G,1)=\sum\limits_{i=1}^{r}ib_{i}$ while $F^{\prime}(G,1)=Q(1)\neq 0$, which implies that $F^{\prime}(G,1)$ is a nonzero integer. Moreover, since $\rho_{i}-1>0$ for $2\leq i\leq r$, we have

$$\prod_{i=2}^{r}(\rho_{i}-1)=|Q(1)|=|F^{\prime}(G,1)|=\left|\sum_{i=1}^{r}ib_{i}\right|\geq 1.$$

Then by (2.2) and the AM-GM inequality,

$$n-1 =\sum_{i=2}^{r}(\rho_{i}-1)\geq(r-1)\left(\prod_{i=2}^{r}(\rho_{i}-1)\right)^{1/(r-1)}\geq r-1,$$ (2.3)

where the equality in the first inequality holds if and only if $\rho_{i}$ are all equal for $2\leq i\leq r$. Hence $r\leq n$, which is equivalent to $m\leq 2n-1$.

Moreover, for the case $m=2n-1$, we have $r=n$ and all the equalities in (2.3) hold. Therefore, $\rho_{i}$ are all equal for $2\leq i\leq r$. Then by (2.2),

$$n-1=\sum_{i=2}^{r}(\rho_{i}-1)=\sum_{i=2}^{n}(\rho_{i}-1),$$

which implies that $\rho_{i}=2$ for all $2\leq i\leq r$. Hence $F(G,\lambda)=(\lambda-1)(\lambda-2)^{n-1}$. ∎

3 The proof of Theorem 6

In this section, we shall prove Theorem 6 by the following lemma established in [4].

Lemma 11 ([4]).

Suppose that $G$ is a $3$-edge-connected graph with $|V(G)|=n$ such that $G$ has only real roots. Let $k=\left|\{v\in V(G):d_{G}(v)>3\}\right|$. If $n\geq 3$ and $G$ has no proper $3$-edge-cut, then $n\geq 2k+1$, and

$$m\geq 2n+2k-3+\frac{4(k-1)^{2}}{n-2k}.$$ (3.1)

Proof of Theorem 6. By Theorems 4 and 5, it suffices to show that if $G$ has only real flow roots, then $G$ has only integral flow roots. Suppose that $G$ is a counterexample to the above statement with the minimum number of edges. Then $G$ has only real flow roots and contains a non-integer flow root $x$. Let $|V(G)|=n$, $|E(G)|=m$, and $k=\left|\{v\in V(G):d_{G}(v)>3\}\right|$.

Claim 1.

$G$ is loopless.

Proof. Assume that $G$ contains a loop $e$. Then by Lemma 8 (i), $G-e$ has only real flow roots and contains the non-integer flow root $x$ with $|E(G-e)|<|E(G)|$, a contradiction to the assumption of $G$. Hence $G$ is loopless. $\natural$

Claim 2.

$G$ is connected.

Proof. Assume that $G$ is disconnected with components $G_{1},G_{2},\dots,G_{c}$, where $c\geq 2$ and $|E(G_{i})|>0$ for all $1\leq i\leq c$. Then by Lemma 8 (ii), each $G_{i}$ has only real flow roots and some $G_{i}$ has the non-integer flow root $x$, where each $G_{i}$ contains less edges than $G$, a contradiction to the assumption of $G$. Hence $G$ is connected. $\natural$

Claim 3.

$G$ is nonseparable with $n\geq 2$.

Proof. If $n=1$, then $m=0$ due to Claim 1. As a result, $F(G,\lambda)=1$, a contradiction to the assumption of $G$. Thus $n\geq 2$. By Claims 1 and 2, it remains to show that $G$ contains no cut-vertices.

Assume that $G$ contains cut-vertices, which implies that $G$ has blocks $G_{1},G_{2},\dots,G_{b}$, where $b\geq 2$ and $|E(G_{i})|>0$ for all $1\leq i\leq b$. Then by Lemma 8 (iii), each $G_{i}$ has only real flow roots and some $G_{i}$ has the non-integer flow root $x$, where each $G_{i}$ contains less edges than $G$, a contradiction. Hence Claim 3 holds. $\natural$

Claim 4.

$G$ is $3$-edge-connected.

Proof. By Claims 2 and 3, it remains to show that $G$ contains no edge-cut of size two.

Assume that $G$ contains a 2-edge-cut $S$, where $e\in S$. Then by Lemma 8 (iv), $G/e$ has only real flow roots and contains the non-integer flow root $x$ with $|E(G-e)|<|E(G)|$, a contradiction. Hence Claim 4 holds. $\natural$

Claim 5.

$G$ has no proper $3$-edge-cut.

Proof. Assume that $G$ has a proper $3$-edge-cut $S$, whose removal separates $G$ into two subgraphs $H_{1}$ and $H_{2}$. Then $|E(H_{1})|,|E(H_{2})|>0$. Let $G_{i}$ be the graph obtained from $G$ by contracting $E(H_{3-i})$ for $i=1,2$. Then by Lemma 8 (v), $G_{1}$, $G_{2}$ have only real flow roots and at least one of $G_{1}$, $G_{2}$ has the non-integer flow root $x$, where $G_{1},G_{2}$ both contain less edges than $G$, a contradiction. Hence Claim 5 holds. $\natural$

Claim 6.

$n\geq 4$.

Proof. Suppose $n=2$. Since $G$ is 3-edge-connected by Claim 4, there are at least three edges in $G$, implying that $m\geq 3=n+1$. Then Lemma 10 indicates that $m\leq 2n-1=3$. Hence $m=3=2n-1$. Then again by Lemma 10, $F(G,\lambda)=(\lambda-1)(\lambda-2)$, a contradiction to the assumption of $G$.

Suppose $n=3$. Since $G$ is 3-edge-connected, the minimum degree of $G$ is at least three, implying that $2m\geq 3n=9$. Thus $m\geq 5>n+1$. Consequently, Lemma 10 indicates that $m\leq 2n-1=5$. Hence $m=5=2n-1$. Then by Lemma 10, $F(G,\lambda)=(\lambda-1)(\lambda-2)^{2}$, also a contradiction to the assumption of $G$.

Then by Claim 3, the claim holds. $\natural$

Claim 7.

$n\geq 2k+1$.

Proof. By Claims 4, 5 and 6, we have $n\geq 4$ and $G$ is a $3$-edge connected graph which has no proper $3$-edge-cut. Then, Lemma 11 implies that $n\geq 2k+1$. $\natural$

Claim 8.

$k=0$.

Proof. Suppose that $k\geq 2$. Since $n\geq 2k+1$ by Claim 7, we have $\frac{4(k-1)^{2}}{n-2k}\geq 0$. Then (3.1) indicates

$$m\geq 2n+2k-3+\frac{4(k-1)^{2}}{n-2k}\geq 2n+2k-3>2n-1,$$

a contradiction to Lemma 10.

Suppose that $k=1$. (3.1) indicates

$$m\geq 2n+2-3=2n-1.$$

Then by Lemma 10, we have $m=2n-1$ and $F(G,x)=(x-1)(x-2)^{n-1}$, a contradiction to the assumption of $G$.

Hence $k=0$. $\natural$

Claim 9.

$n=4$.

Proof. By Claim 4, every vertex in $G$ has degree at least three, while by Claim 8, every vertex in $G$ has degree at most three. Hence $G$ is cubic and $m=3n/2$. Then (3.1) indicates

$$\frac{3n}{2}\geq 2n-3+\frac{4}{n},$$

or equivalently

$$(n-2)(n-4)\leq 0.$$

Thus $n=4$ follows from Claim 6. $\natural$

Claim 10.

$G$ has only integral roots.

Proof. Now $G$ is a cubic, $3$-edge-connected and loopless multigraph on four vertices. We shall show that $G$ is $K_{4}$. Equivalently, we shall prove that $G$ contains no parallel edges.

Suppose that $G$ has parallel edges between vertices $u,v$ in $G$. Then there are at most two edges between $\{u,v\}$ and $V(G)\setminus\{u,v\}$ in $G$, which indicates an edge-cut of size at most two in $G$, a contradiction to the fact that $G$ is $3$-edge-connected. Consequently, $G$ is $K_{4}$, where

$$F(K_{4},\lambda)=(\lambda-1)(\lambda-2)(\lambda-3).$$

Hence the claim holds. $\natural$

Claim 10 contradicts the assumption of $G$. The theorem is proven. ∎