{'fraction_non_alphanumeric': 0.043384152079804256, 'fraction_numerical': 0.014680971202710334, 'mean_word_length': 3.813816534541336, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graphs whose flow polynomials have only integral roots

We show if the flow polynomial of a bridgeless graph G has only integral roots, then G is the dual graph to a planar chordal graph. We also show that for 3-connected cubic graphs, the same conclusion holds under the weaker hypothesis that it has only real flow roots. Expressed in the language of matroid theory, this result says that the cographic matroids with only integral characteristic roots are the cycle matroids of planar chordal graphs.


Introduction
For each different type of polynomial associated with a graph or matroid, a natural and usually well-studied question is to determine if and when the polynomial factors completely over the integers, or equivalently, has only integer roots. For example, consider the chromatic polynomial P (G; λ), which is defined to be the number of ways of properly coloring the vertices of the graph G with at most λ colors. The chromatic roots of G are the roots of the chromatic polynomial of G, and it has been a long-standing open question to characterize the graphs with integral chromatic roots. Chordal graphs, which are defined to be graphs with no induced cycles of length greater than 3, have integral chromatic roots, but there are also many non-chordal graphs with this property (see [4,5,6,8]), and a complete characterization seems difficult, and perhaps even impossible.
The polynomial dual to the chromatic polynomial is the flow polynomial F (G; λ), defined to be the number of nowhere-zero flows on the graph G taking values in an abelian group of order λ (see Tutte [15], Brylawski and Oxley [2]). The roots of F (G; λ) are called the flow roots of G, and in this paper we characterize the graphs with integral flow roots. As the chromatic polynomial of a planar graph is the flow polynomial of its dual (up to a factor of a power of λ), the duals of planar chordal graphs provide obvious examples of graphs with integral flow roots. Using an inequality for coefficients of polynomials with real roots, an algebraic argument (first used in [12]) to extract information from the coefficients of the flow polynomial, and a product formula from matroid theory, we show that a graph with integral flow roots is the dual of a planar chordal graph. Loosely speaking, our main result shows that the obvious examples are the only examples. We note that Theorem 1.1 implies the theorem of Dong and Koh [5] that planar graphs with integral chromatic roots are chordal.
Simple planar chordal graphs have a very restricted structure. A 2-connected planar chordal graph is constructed by starting from a triangle K 3 and then repeatedly joining a new vertex either to both ends of an edge or to three vertices of a triangular face. The operation of joining a new vertex to an edge creates a 2-vertex-cutset which persists throughout any subsequent operations, and so the graph is 3-connected if and only if it arises from the complete graph K 4 by repeatedly inserting a vertex of degree 3 into a face. Thus the 3-connected planar chordal graphs form a very special class of triangulations, in fact precisely the class of uniquely 4-colorable planar graphs (Fowler [7]). At the other extreme are the graphs obtained from a triangle by using only the first operation of joining a new vertex to an edge (i.e., never creating a K 4 ). These graphs are called 2-trees and it is well known that they are maximal series-parallel graphs with respect to edge addition.
We develop and present our results in the more general context of matroid theory because the chromatic and flow polynomials of graphs are just the characteristic polynomials of specific classes of matroids, whereas the main ideas in our proof apply in general. Furthermore, there are various other natural classes of matroids where it may be possible to characterize the matroids whose characteristic polynomials have only integer roots. We briefly discuss questions and conjectures of this nature in Section 6.

Preliminaries
Recall that the characteristic polynomial χ(M ; λ) of a matroid M is defined in the following way: if M has a rank-0 element, then χ(M ; λ) = 0 and if M has no rank-0 elements, it is defined by where L(M ) is the lattice of flats of M and µ is its Möbius function (see [13]). We call the roots of χ(M ; λ) the characteristic roots of M. If M has no rank-0 elements, then the characteristic polynomial of M depends only on its lattice of flats. The simplification of a matroid M is the matroid obtained from M by removing all rank-0 elements and deleting all but one element in each rank-1 flat. The lattice of flats is unchanged under simplification; hence, if a matroid starts off with no rank-0 elements, the characteristic polynomial is also unchanged.
Chromatic and flow polynomials of graphs are special cases of characteristic polynomials of matroids: indeed, P (G; λ) = λ c χ(M (G); λ), where M (G) is the cycle matroid of G and c is the number of connected components in G, and F (G; λ) = χ(M ⊥ (G); λ), where M ⊥ (G), the cocycle matroid of G, is the dual of M (G). In particular, note that the flow polynomial F (G; λ) depends only on the simplification of M ⊥ (G).
A cutset C in a graph G is a set of edges such that G − C has more connected components than G. A bridge in a graph is a cutset of size 1, and if G has a bridge, then its flow polynomial is identically zero. In matroid terms, the cocycle matroid M ⊥ (G) has a rank-0 element and so its characteristic polynomial is identically zero. To avoid this degenerate case, we henceforth consider only bridgeless graphs.
If G has no bridges, but is disconnected or has a cut-vertex, then it is either the disjoint union of two smaller graphs G ′ and G ′′ or it is obtained by identifying a vertex of G ′ with a vertex of G ′′ . In either case, the flow polynomial of G is determined purely by the flow polynomials of G ′ and G ′′ : This situation causes no difficulty however because it is easy to see that if G ′ and G ′′ are the duals of planar chordal graphs, then so is G. In matroid terms, the cocycle matroid M ⊥ (G) is disconnected and equal to the direct sum If G is 2-vertex-connected, but has a 2-cutset, then its flow polynomial is unchanged if one of the edges in the cutset is contracted, and this process can be repeated until the graph is 3-edge-connected. A vertex of degree 2 necessarily yields a 2-cutset, but not all 2-cutsets arise in this manner. In matroid terms, any 2-cutset corresponds to a series pair in the cycle matroid M (G) and hence a parallel pair in the cocycle matroid M ⊥ (G). Therefore the process of repeatedly contracting an edge in a 2-cutset until no 2-cutsets remain is just simplifying the cocycle matroid. It proves convenient for us to work with simple matroids, but it is important to note that this implies the main result even if the original matroid is not simple. To see this, suppose that the simplification of M ⊥ (G) is the cycle matroid of a simple planar chordal graph H. Then M ⊥ (G) is the cycle matroid of the graph obtained from H adding some edges in parallel to existing edges. As this process does not alter planarity or the property of being chordal, the resulting graph is still planar and chordal, though no longer simple.
A crucial step in the proof of Theorem 1.1 is to show that certain minimal 3-cutsets exist in any graph whose flow polynomial has integer roots. Minimal 3-cutsets have rank 2 and are closed; hence, they form a 3-point line in M ⊥ (G). In a 3-edge-connected graph G, we call a minimal 3-cutset proper if its deletion separates G into disjoint subgraphs G ′ and G ′′ , each containing at least one edge. An improper 3-cutset necessarily consists of the 3 edges incident on a vertex v of degree 3.
Since deletion in the graph G corresponds to contraction in the cocycle matroid M ⊥ (G), a proper 3-cutset L induces the following (non-trivial) separation in the cocycle matroid: In turn, this separation induces a product formula for flow polynomials.
Lemma 2.1. Suppose that the graph G has a minimal 3-cutset L. Let G 1 and G 2 be the two graphs G G ′′ and G G ′ obtained by contracting each side of the cutset to a single vertex. Then We remark that an improper 3-cutset associated with a vertex v may induce a non-trivial separation. This occurs if and only if when v and its incident edges are deleted, the resulting graph has a new cut-vertex. The formula in Lemma 2.1 is a special case of a matroid formula of Brylawski for generalized parallel connection over a modular flat (see [1] and [2], p. 205), and it appeared in this form as Lemma 29 in Jackson's survey [9]. Figure 1 shows a graph G with a minimal 3-edge cutset, and the graph G 1 formed by contracting one side of the cut. In this case, G 2 is the graph K 4 which has flow polynomial The reader may recognize the formula (2) as the flow analogue of the formula for the chromatic polynomial of the "join" of two graphs at a triangle, which has a simple counting proof. Lemma 2.1 can be proved in several ways, in particular, by a routine contraction-and-deletion argument. It is a little harder to give a direct counting argument analogous to the chromatic polynomial case, but this can be done by considering flows with values in the direct product Z m 2 of m copies of the integers modulo 2, exploiting the fact that the flow polynomial depends only on the order of the group and not its structure.

Polynomials with only real roots
We will use the following easy result about polynomials. This simple lemma is surely known but we are unable to find a reference.
There are three kinds of terms in the sum for e m (λ 1 , λ 2 , . . . , λ n ). The first are those terms not containing λ 1 or λ 2 , which are unchanged when we change λ 1 and λ 2 to ν. The second are those terms containing exactly one of λ 1 or λ 2 . These terms come in pairs, λ 1 λ i2 · · · λ im and λ 2 λ i2 · · · λ im . The sum of the two terms in each pair is unchanged when ν is substituted for λ 1 and λ 2 . The third kind of terms are those containing both λ 1 and λ 2 . Then by the arithmetic-geometric mean inequality, where the inequality is strict when λ 1 = λ 2 . Therefore these terms strictly increase when ν is substituted for λ 1 and λ 2 .
The proof of Lemma 3.1 can be easily adapted to prove a variation.
Lemma 3.2. Suppose that the polynomial p(λ) in the previous lemma has n positive integer roots λ 1 , λ 2 , . . . , λ n such thatλ is not an integer. Let λ * = ⌊λ⌋, λ * = ⌈λ⌉, and δ be the positive integer such that Then the coefficient a m is at most the value of the degree-m symmetric function evaluated with n − δ variables set to λ * and δ variables set to λ * . In particular,

Three-element circuits
In this section we find lower bounds on the number of 3-element circuits in a matroid whose characteristic polynomial has only real or integer roots. Note that the size 3r − 3 that occurs in both lemmas in this section is the maximum number of elements in a simple cographic rank-r matroid. Recall that a line in a matroid is a rank-2 flat.
Let γ i be the number of lines in M with i elements, so γ 3 is the number of 3-element circuits. By hypothesis, γ i = 0 if i ≥ 4. From standard results on characteristic polynomials of matroids, the coefficients of λ r−1 and λ r−2 in χ(M ; λ) are equal to the number of elements e and e 2 − γ 3 respectively. Thus we have b 1 + 3 = 3r − 3, and so If all the roots of χ † (M ; λ) are real then, because b 1 = 3(r − 2), we can apply Lemma 3.1 to χ † (M ; λ) withλ = 3 and conclude that On substituting this inequality into the equation given above for γ 3 , we conclude that γ 3 ≥ 3r − 5.

Equality occurs if and only if the inequality (3) is an equality, that is, when
For matroids with fewer elements, we can get an analogous lower bound on the number of 3-element circuits, but at the cost of the stronger assumption that the characteristic polynomial has integer roots, rather than real roots.

Graphs with integral flow roots
In this section we apply the results of the previous section to flow polynomials. Let G be a 3-edge-connected graph with vertex set V and edge set E, v i be the number of vertices of degree i, and r be the rank of its cocycle matroid M ⊥ (G). Then Let δ be defined by Then |V | = 2r − 2 − δ, and |E| = 3r − 3 − δ.
We shall prove Theorem 1.1 in the following form. Proof. We prove the result by induction on the rank r. The cographic matroids of rank 3 or less are planar graphic, and it is easy to check that the theorem holds in this case. Thus, we may assume that r ≥ 4. If M is not connected and equals M ′ ⊕ M ′′ , then χ(M ; λ) = χ(M ′ ; λ)χ(M ′′ ; λ). Hence, χ(M ′ ; λ) and χ(M ′′ ; λ) have integer roots and we can apply induction. We can now suppose that M is simple and connected, and thus, we can find a 2-vertexconnected, 3-edge-connected graph G with vertex set V and edge set E such that Let δ be defined as in Equation (6). Using the result that that (λ − 1) 2 divides χ(M ; λ) if and only if M is not connected (see, for example, [3]), we may assume that χ(M ; λ) has exactly one root equal to 1 and all other roots integers greater than or equal to 2. Thus, |E| ≥ 2r − 1, that is, We distinguish two cases: δ ≤ r − 3 and δ = r − 2. Suppose first that δ ≤ r − 3. By Lemma 4.2 the matroid M has at least 3r − 5 − 2δ 3-circuits. A circuit in the cographic matroid M corresponds to a minimal cutset in the graph G, and so G has at least 3r − 5 − 2δ minimal 3-cutsets. Of these, there are v 3 cutsets separating a vertex of degree 3 from the subgraph on the other vertices. Since proper minimal 3-cutsets. Since δ > 0 if and only if there is at least one vertex of degree greater than 3, we conclude that G has least one proper minimal 3-cutset L. Let G 1 and G 2 be the two graphs obtained from G and L as defined in Lemma 2.1 (and illustrated in Figure 1). By Lemma 2.1, the flow polynomials of G 1 and G 2 have only integral roots and by induction, both G 1 and G 2 are the duals of planar chordal graphs. The graph G is obtained from G 1 and G 2 by identifying the three edges incident with a vertex of G 1 with the three edges incident with a vertex of G 2 . In the planar dual, this corresponds to forming G ⊥ by identifying a triangular face of G ⊥ 1 with a triangular face of G ⊥ 2 . Identifying a face in each of two planar graphs gives a planar graph, and identifying a clique in each of two chordal graphs yields a chordal graph. Hence, G is the dual of a planar chordal graph.
To finish the proof, we consider the case when δ = r − 2. In this case, χ(M ; λ) = (λ − 1)(λ − 2) r−1 , the graph G has 2r − 1 edges, r vertices, and by Lemma 4.2, has at least r − 1 minimal 3-cutsets. If G has r or more minimal 3-cutsets, then as in the first case, G has a proper minimal 3-cutset and we can apply induction. Thus, we may assume that G has exactly r − 1 minimal 3-cutsets, none of which is proper. It follows that r − 1 vertices in G have degree 3, and so if d is the degree of the last vertex then 2|E| = 2(2r − 1) = 3(r − 1) + d, and so d = r + 1. By Lemma 5.2, G is the dual of a 2-tree and hence dual to a planar chordal graph.
Lemma 5.2. A 2-vertex-connected graph G with r vertices of which r − 1 have degree 3 and one has degree r + 1 is the planar dual of a 2-tree.
Proof. We prove this by induction on r. When r = 2, the graph is a triple-edge which is the planar dual of K 3 . So suppose that r > 2 and denote the vertex of degree r + 1 by v. As G is 2-vertex-connected, v is not connected by a triple-edge to any other vertex, but as r + 1 > r − 1, it must be joined by a double-edge to some vertex u where u has a single further neighbor that we denote w. The graph obtained by deleting the double-edge and identifying u and v is 2-vertex-connected and has r − 1 vertices, of which r − 2 have degree 3 and one has degree r, and hence by induction it is the planar dual of a 2-tree T . It is straightforward to see that adding a new vertex in the face of size r adjacent to the edge {v, w} of T (under the convention that edges of a graph are identified with those of its planar dual) yields a 2-tree whose dual is G.
Lemma 5.2 shows that when δ = r − 2, the matroid M is the cycle matroid of a maximal series-parallel graph. It might be useful to give an alternative (but equivalent) argument more congenial to matroid theorists. As in the proof of the lemma, one shows that there is a vertex u in G of degree 3 incident on a double-edge, which we label a and b, and a single edge, which we label c. Observe that if we assume that M has 3r − 3 elements or, equivalently, the graph G is a cubic graph, then we can use Lemma 3.1 instead of Lemma 3.2 to obtain the following result. Theorem 5.3. If a 3-connected cubic graph G has real flow roots, then G is the dual of a chordal planar triangulation.
We do not know whether Theorem 5.1 holds if the hypothesis is weakened so that we only assume that all the roots of χ(M ; λ) are real. Using Lemma 4.3(a), we can show that if M is a rank-r cographic matroid with real characteristic roots and δ < 2(r − 2), then M is the cycle matroid of a planar chordal graph.

Supersolvable Matroids
In the remainder of this paper, we shall describe the matroid-theoretic aspects of Theorem 5.1. We shall only consider matroids with no rank-0 elements.
Recall that a flat X in a matroid M is modular if for every line L in M such that rank(X ∨ L) = rank(X) + 1, X ∩ L is non-empty (and hence a point or a rank-1 flat). If X is a modular flat, then the characteristic polynomial χ(M |X; λ) of the restriction of M to X divides the characteristic polynomial of χ(M ; λ) (see Stanley [14]). A rank-r matroid M is supersolvable if there exists a maximal chain of modular flats X 0 , X 1 , X 2 , . . . , X r , with X i−1 ⊂ X i and rank(X i ) = i. A maximal chain of modular flats forces a complete factorization of χ(M ; λ) over the integers. Explicitly, the characteristic roots are |X i | − |X i−1 |, i = 1, 2, . . . , r.
The next lemma describe how a modular copoint forces a complete subgraph. The first part of the lemma holds for arbitrary matroids (Lemma 5.14 in [10]). Proof. Let I be an independent set of size d in D. Since X is modular, every line outside X meets X at a point. Hence each pair of points in I determines a point of intersection in X, and because I is independent, these points are distinct. The If M has no M (K 5 )-submatroid, then d ≤ 3, and D equals a point, two points, three independent points, or a 4-circuit, corresponding to the four cases listed in the lemma.
A simple chordal graph G can be built beginning with a vertex and repeatedly adding a new vertex and all edges from that vertex to a complete subgraph. This construction yields a maximal chain of modular flats and hence, the cycle matroid M of G is supersolvable. On the other hand, Lemma 6.1 implies that if the cycle matroid of a graph G is supersolvable, then G is chordal. We can now restate Theorem 5.1 for matroids. Proof. To show that (1) implies (2), we use the induction argument in the proof of Theorem 5.1, using as hypothesis the description of M as a parallel connection. Note that if we take parallel connections of three M (K 4 )'s at a common line, then we obtain an M (K 3,3 )-submatroid, which cannot occur inside a cographic matroid. That (2) implies (3), (3) implies (4), and (4) implies (1) follow from results discussed earlier.
Although we proved directly that cographic matroids with integer roots are the cycle matroids of planar chordal graphs, it can be useful to view this as the combination of two separate results: (1) A cographic matroid with integral characteristic roots is supersolvable.
(2) A supersolvable cographic matroid is the cycle matroid of a planar chordal graph.
The second of these results can be proved with a direct argument. Kuratowski's theorem says that if a graph is not planar, then it has a subgraph which is a series extension of K 5 or K 3,3 . Dualizing, we conclude that if M is the cocycle matroid of a non-planar graph, then there is some set of elements X such that the contraction M/X is a parallel extension of M ⊥ (K 5 ) or M ⊥ (K 3,3 ). However, these latter matroids are not supersolvable, and as contraction preserves supersolvability, it follows that M itself is not supersolvable. Hence, if M is supersolvable and cographic, it is the cocycle matroid of some planar graph, that is, M is the cycle matroid of a planar graph, and hence the cycle matroid of a chordal graph.
When considering generalizations of our results to other classes of matroids, it is natural to consider the two questions separately, i.e., asking which other classes of binary matroids have the property that only supersolvable matroids have integral characteristic roots, and then separately characterizing the supersolvable matroids in the class. Theorem 6.2 and Lemma 6.1 suggest the conjecture that a binary matroid with no M (K 5 )-minor with integral characteristic roots is supersolvable.
We end by mentioning that if we remove the restriction that the matroid is binary, there are many non-supersolvable matroids with integral characteristic roots. See, for example, [11]. In the context of matroids, chromatic and flow polynomials would seem to be very special cases.