INDEPENDENT SETS AND CONTINUED FRACTIONS

SWEE HONG CHAN, STEVEN HEILMAN, GRETA PANOVA

Abstract. Linek’s 1989 problem asks whether the numbers of independent sets of trees avoid infinitely many positive integers. We show that the set of natural numbers realized as the number of independent sets of a tree has a lower growth exponent of 0.1966. We further prove that the set of positive integers representable by connected planar graphs has asymptotic density one. Lastly, we establish a phase transition: the number of independent sets of graphs with fewer than d|V | edges for any d < 1 is contained in a set of density zero, whereas, following Shkredov’s recent breakthrough on Zaremba’s conjecture in continued fraction theory, there exists a constant D such that the number of independent sets of graphs with at most D|V | edges covers all positive integers.

1. Introduction

An independent set in a graph is a set of vertices no two of which are adjacent. For a graph G, let i(G) denote the number of independent sets of G. This quantity is also known as the Merrifield–Simmons index or the Fibonacci number of a graph. Independent sets are among the most basic and most studied objects in graph theory, appearing in extremal graph theory, Ramsey theory, graph coloring, the hard-core model [DK25], and theoretical computer science [Gre00, Wei06, Sly10].

The possible values for graphs on n vertices range from linear to exponential: the complete graph K_{n} has i(K_{n}) = n + 1, whereas the edgeless graph has 2^{n} independent sets. Without any restrictions on the graph, the inverse problem is trivial: every positive integer m has at least one graph G with i(G) = m. In this paper, we study the inverse problem for the map i, which becomes considerably more challenging when the class of allowable graphs is restricted. Specifically, we ask:

Which integers can occur as i(G) when G is drawn from specific classes?

The first to systematically study this inverse problem for restricted classes of graphs was Linek [Lin89], who demonstrated that i: {bipartite graphs} → ℕ = {1, 2, 3, …} is surjective. He further observed that this result does not extend to the more restrictive class of trees, as he found specific integers that cannot be realized as the number of independent sets of any tree. This prompted him to pose the following question:

Date: April 20, 2026.

Email: sweehong.chan@rutgers.edu, stevenmheilman@gmail.com, gpanova@usc.edu S.H.C. is supported by NSF Grant DMS 2246845. S.H. is supported by NSF Grant CCF AF 2448108. G.P.

is supported by NSF Grant CCF AF 2302174.

MSC Classification: 05C69, 11A55, 05C05, 05C10 Keywords: Independent set, continued fraction, planar graph, tree Department of Mathematics, Rutgers University, Piscataway, NJ, 08854.

Department of Mathematics, University of Southern California, Los Angeles, CA 90089.

Problem 1.1 (Linek’s Problem [Lin89]). Are there infinitely many positive integers that are not the number of independent sets of a tree?

Virtually no real progress has been made on this problem over the last 35 years. Part of the reason this problem is so difficult is that traditional approaches, such as gadgets and constructions emulating addition and multiplication or those relying on randomized constructions, fail due to Wagner’s observation [Wag09] that almost all random trees have an even number of independent sets (a result further generalized to F -matchings by Alon– Haber–Krivelevich [AHK11]). In fact, [AHK11] implies that a large random tree will have a large number of distinct prime factors, implying that a random tree T will rarely satisfy that i(T) is prime, for example, which will not give a negative answer to Problem 1.1.

On the computational front, Law [Law12] verified that among the integers up to 832040, only 823 fail to occur as the number of independent sets of a tree, and the largest missing value is 88013. In this paper, we extend this evidence substantially: we verify computationally that every integer between 88014 and 30 million is realized as the independent set number of some tree. The missing values are included in the appendix. ^{1} This computational evidence convinces us to make the following conjecture.

Conjecture 1.2 (Effective Linek’s Problem). Every integer greater than 88013 appears as the number of independent sets of some tree.

We remark that this conjecture contrasts with a recent conjecture by Han et al. [HHK^{+}25], who conjectured that there exist infinitely many positive integers that cannot be realized as the number of independent sets of any tree.

In this paper, we seek to advance the frontier of Linek’s Problem 1.1 by establishing theoretical results concerning three sparse graph classes: trees, connected planar graphs, and graphs of bounded average degree. Our focus on sparse graphs is motivated by the observation that the difficulty of Linek’s Problem for trees likely stems from the lack of edges, which are useful in controlling the occurrence of independent sets. Indeed, the result of Linek for bipartite graphs relied on dense constructions with Ω(|V |^{2}) edges, whereas Problem 1.1 is for the sparsest connected graphs.

Our main results are as follows:

• For connected planar graphs, we prove that almost every positive integer occurs as a number of independent sets.

• For trees, we show that the number of attainable independent set values up to N grows at least as large as N^{.1966}.

• For graphs of bounded average degree, we prove a phase transition: below average degree 2, only a density-zero set of integers can occur as the number of independent sets, whereas above some absolute constant average degree, every positive integer occurs.

Thus, compared with Linek’s original bipartite construction, our results show that graphs with only O(|V |) edges already suffice to realize almost all, and in some regimes all, positive integers. We state these three results formally below.

1The verification code appears in GitHub https://github.com/sheilman77/independent sets/

1.1. Trees. For any S ⊆ ℕ, the lower growth exponent of S is

\underline{Exp}(S) := lim inf_{N→∞} \frac{log(|S ∩ \{1, …, N\}|)}{log N}.

We denote by I_{tree} ⊆ ℕ the set of natural numbers that can be expressed as the number of independent sets of some tree.

I_{tree} := { i(T) | T is a tree }.

We also use the Vinogradov notation that f(N) ≪ g(N) means that there exists a constant C > 0 such that f(N) ≤ Cg(N) for all sufficiently large N.

Theorem 1.3. The lower growth exponent of I_{tree} satisfies

\underline{Exp}(I_{tree}) ≥ \frac{log_{τ} 2}{4} ≈ 0.1966, where τ := 1 + \sqrt{2}.

Equivalently,

| I_{tree} ∩\{1, …, N\}| ≫ N^{\frac{log_{τ} 2}{4} −o(1)} ≈ N^{0.1966}.

We remark that the primary goal of Theorem 1.3 is to establish a strictly positive lower bound on the lower growth exponent, as we do not attempt to optimize the numerical lower bound. We conjecture that a stronger version of Theorem 1.3 holds, which can also be viewed as another weak form of Linek’s Problem 1.1.

Conjecture 1.4 (Density Linek’s Problem). The set I_{tree}, consisting of integers expressible as the number of independent sets of some tree, has positive lower density, i.e.

lim inf_{N→∞} \frac{| I_{tree} ∩\{1, …, N\}|}{N} > 0.

In fact, Conjecture 1.4 would follow from Hensley’s Conjecture in number theory. See Section 6.1 for further discussion on this point.

1.2. Planar graphs. Denote by I_{pla} ⊆ ℕ the set of integers that can be expressed as the number of independent sets of some connected planar graph,

I_{pla} := { i(P) | P is a connected planar graph }.

Let ℕ := \{1, 2, 3, …\}. The density of a subset S ⊆ ℕ is the quantity lim_{N→∞} \frac{|S∩\{1,...,N\}|}{N}, if the limit exists. We say that S contains almost every integer if S has density 1.

Theorem 1.5. Almost every positive integer can be expressed as the number of independent sets of some connected planar graph. That is, the set I_{pla} has density 1.

We conjecture that a stronger version of Theorem 1.5 holds, which can also be viewed as a weak form of Linek’s Problem 1.1.

Conjecture 1.6 (Planar Linek’s Problem). All positive integers can be expressed as the number of independent sets of some connected planar graph.

This conjecture is further supported by computation, as connected planar graphs realize all 823 values missing from Law’s tree computation. Note that we consider the empty graph to be a connected planar graph.

1.3. Graphs with bounded average degree. The average degree d(G) of a nonempty graph G = (V, E) is defined as 2|E|/|V |. Let d > 0. We denote by I_{d} ⊆ ℕ the set

I_{d} := { i(G) | G is a graph with d(G) ≤ d }.

Here we do not require G to be connected. We also define d(empty graph) := 0.

Theorem 1.7. There exists a fixed constant D > 0 such that the following holds (1) If d ∈ (0, 2), then there exist constants 0 < c_{1}(d) ≤ c_{2}(d) < 1 such that

N^{c_{1}(d)} ≪ | I_{d} ∩ {1, …, N}| ≪ N^{c_{2}(d)}.

(2) If d ≥ D, then every positive integer appears in I_{d}.

We conjecture that the size of I_{d} exhibits a sharp phase transition and that one can choose D = 2 in the above theorem.

Conjecture 1.8. If d ≥ 2, then all but finitely many positive integers appear in I_{d}.

In fact, computations suggest that the only positive integers not appearing are 71 and 191, though edge densities 20/9 and 24/11 can be achieved for those, respectively.

That is to say, if the average degree is strictly below 2, then the possible numbers of independent sets are restricted to a set of integers with a density of zero, whereas for an average degree at least 2, every positive integer is achievable (except two). Naturally, a negative answer to Linek’s Problem 1.1 would imply the above conjecture. Specifically, we have that Conjecture 1.2 (effective Linek’s problem) ⟹ Negative answer to Linek’s problem 1.1 ⟹ Conjecture 1.4 (density Linek’s Problem) and Conjecture 1.8 (sharp phase transition at d = 2). We also note a key distinction between the assumptions of Theorem 1.7 (for graphs with bounded average degree) and those of Theorems 1.3 (for trees) and 1.5 (for connected planar graphs): we do not require the graphs to be connected in the former, whereas we do require them to be connected in the latter.

All three results are proved by applying a connection between independent set counts and continued fractions. The proof of Theorem 1.3 (trees) draws inspiration from the work of Alon–Bucić–Gishboliner [ABG25], and is relatively elementary. In contrast, the proof of Theorem 1.5 (planar graphs) requires the more advanced Bourgain–Kontorovich theory [BK14]. For Theorem 1.7 (graphs with bounded average degree), the subcritical regime builds on Theorem 1.5 together with standard enumerative arguments, while the supercritical regime uses Shkredov’s breakthrough on Zaremba’s conjecture [Shk26]. It is worth noting that the phase transition in Theorem 1.7 does not strictly require Shkredov’s result; applying Theorem 1.5 instead yields a similar transition, but with the weaker guarantee that I_{d} is a set of density 1 in part (2). Our continued-fraction viewpoint is in the same spirit as the recent work of Chan–Kontorovich–Pak [CKP24] on Sedláček’s problem for spanning tree counts.

The paper is organized as follows. In Section 2, we recall various results on continued fraction theory and Zaremba’s conjecture. In Sections 3, 4, and 5, we prove Theorems 1.3, 1.5, and 1.7, respectively. We conclude with a discussion in Section 6.

2. Zaremba’s Conjecture

In this section, we review results related to Zaremba’s conjecture in number theory, which will play a crucial role in the proofs of the main results.

For positive integers a_{1}, …, a_{ℓ} ≥ 1, the corresponding continued fraction is

[a_{1}, a_{2}, …, a_{ℓ}] := \frac{1}{a_{1} + \frac{1}{a_{2} + ⋯ + \frac{1}{a_{ℓ}}}}.

It follows from the Euclidean algorithm that every rational number in the interval (0, 1) admits a continued fraction expansion. One of the longstanding open problems in continued fraction theory is the following conjecture of Zaremba [Zar72]. For a positive integer A, let Q_{A} denote the set of denominators of continued fractions whose partial quotients are bounded by A, i.e.

Q_{A} := {q ∈ ℕ: ∃ p ∈ ℕ with p < q such that gcd(p, q) = 1
and \frac{p}{q} = [a_{1}, …, a_{ℓ}] with a_{1}, …, a_{ℓ} ≤ A\} ∪ \{1\}.

Conjecture 2.1 (Zaremba’s Conjecture [Zar72]). For A = 5, the set Q_{A} consists of all positive integers.

Virtually no progress was made on this conjecture until the breakthrough work of Bourgain and Kontorovich [BK14], who showed that the set Q_{A} has density 1 for A = 50. This result was subsequently improved to A = 5 by Huang [Hua15]. The latter will be a key result used in this paper, so we state it below.

Theorem 2.2 ([Hua15, Thm 1.6]). For A = 5, the set Q_{A} has density equal to 1.

We will also use the following recent breakthrough result of Shkredov.

Theorem 2.3 ([Shk26, Cor. 1]). There exists an absolute constant A for which the set Q_{A} contains every prime.

3. Trees and the proof of Theorem 1.3

A marked tree (T, v) is an ordered pair consisting of a tree T and a root vertex v of T. We denote by a(T, v) the number of independent sets of T containing v, and b(T, v) the number of independent sets of T not containing v. We have two operations that generate all marked trees when combined together. The first operation is the extension operation, where given a marked tree (T, v), the new tree T′ is obtained by adding a new root vertex v′ that is adjacent to v, and outputting the new marked tree (T′, v′). It follows that

a(T′, v′) := b(T, v), b(T′, v′) = a(T, v) + b(T, v).

The second operation is the product operation, where given marked trees (T_{1}, v_{1}) and (T_{2}, v_{2}), the new tree T_{3} is obtained by taking the disjoint union of T_{1} and T_{2}, followed by identifying v_{1} and v_{2}, and declaring the new vertex to be v_{3}. It follows that

a(T_{3}, v_{3}) = a(T_{1}, v_{1})a(T_{2}, v_{2}), b(T_{3}, v_{3}) = b(T_{1}, v_{1})b(T_{2}, v_{2}).

These operations are standard constructions on trees; and our application here is particularly inspired by [Law10].

Instead of keeping track of (a, b) := (a(T, v), b(T, v)), it is sometimes more convenient to keep track of two parameters (g, r) := (g(T, v), r(T, v)), where

g := gcd(a, b), r(T, v) := \frac{a}{b}.

Note that g is a positive integer, while r is a rational number in (0, 1]. Note that we can recover (a, b) from (g, r) by

a := g × (numerator of r(T, v)), b := g × (denominator of r(T, v)).

where r is written in the reduced form.

Let S be the set of pairs (g, r) such that there exists a marked tree (T, v) for which g = g(T, v) and r = r(T, v).

Lemma 3.1. Suppose that (g, r) ∈ S and (g′, r′) ∈ S, where r′ = 1/k for some positive integer k. Then the pair (g′′, r′′) is contained in S, where

g′′ := gg^{′2}k, r′′ := \frac{1}{k + r}.

Proof. The lemma follows from applying the product operation to (T, v) and (T′, v′) (corresponding to (g, r) and (g′, r′), respectively), followed by the extension operation, then followed by product operation with (T′, v′). Specifically, let a, b, a′, b′ be the corresponding numbers of the two trees. The product operation gives a tree with marked vertex v and pair (aa′, bb′). The extension gives another tree (T′′, v′′) with a(T′′, v′′) = bb′ and b(T′′, v′′) = aa′ + bb′. The final product operation gives a tree (T_{0}, w) with a(T_{0}, w) = bb′a′ = bk(g′)^{2} and b(T_{0}, w) = (aa′+bb′)b′ = (ag′+kbg′)kg′. The ratio is then r(T_{0}, w) = \frac{bkg′g′}{k(a+kb)g′g′} = \frac{b}{a+kb} = \frac{1}{r+k}. The gcd is then g(T_{0}, w) = gcd(bkg′g′, kg′g′(a + kb)) = k(g′)^{2} gcd(b, a) = kg(g′)^{2}. □

Corollary 3.2. We have

S ⊇ \{(1, 1), (1, \frac{1}{2})\} ,

and the corresponding trees have a number of vertices equal to 1 and 2 respectively.

Proof. This follows by choosing the tree with one and two vertices, respectively. □

Let \overline{S} ⊆ S be the subset generated by repeatedly applying the operation to trees described by Lemma 3.1, where at each step (g′, r′) is chosen to be one of the two ordered pairs given in Corollary 3.2.

Lemma 3.3. For every (g, r) ∈ \overline{S},

g ≤ q,

where (p, q) are the unique coprime positive integers such that r = \frac{p}{q}.

Proof. First note that two ordered pairs in Corollary 3.2 clearly satisfy the conclusion of the lemma. Now, let (g, r) be any element satisfying the conclusion of the lemma, let (g′, r′) ∈ \{(1, 1), (1, \frac{1}{2})\} and let (g′′, r′′) be the resulting element from the operation in Lemma 3.1. We now show that (g′′, r′′) also satisfies the conclusion of the lemma.

Let r = \frac{p}{q}, r′ = \frac{1}{k}, and r′′ = \frac{p′′}{q′′}. Suppose that (g′, r′) = (1, \frac{1}{2}). From Lemma 3.1, r′′ = 1/(k + r) = 1/(k + p/q) = q/(kq + p), so q′′ = kq + p. We then have

(3.1)  g′′ = g(g′)^{2}k ≤ q(g′)^{2}k = qk ≤ (kq + p) = q′′,

which proves the claim in this case. The other case proceeds similarly.

The conclusion of the lemma now follows by induction, as desired. □

We now proceed to prove Theorem 1.3. Let N be any sufficiently large positive integer, and let τ := 1 + \sqrt{2}.

Set ℓ := ⌊(log_{τ}(N/2) − 4)/2⌋. Let a_{1}, …, a_{ℓ} be arbitrary elements of {1, 2}. Note that there are 2^{ℓ} many such choices. We define P := P (a_{1}, …, a_{ℓ}) and Q := Q(a_{1}, …, a_{ℓ}) to be the unique coprime positive integers such that

(3.2)  \frac{P}{Q} = \begin{cases}[1, a_{1}, …, a_{ℓ}] & if the denominator of [1, a_{1}, …, a_{ℓ}] is odd; \\ [1, 1, a_{1}, …, a_{ℓ}] & if the denominator of [1, a_{1}, …, a_{ℓ}] is even \end{cases} .

Note that in either case Q is an odd number. Also note that Q is maximized when all a_{i}’s are equal to 2, since P and Q are uniquely expressed as polynomials in the a_{i}s with positive coefficients. It then follows from a direct calculation using the matrix product interpretation

and that the eigenvalues of the matrix (\begin{matrix}0 & 1 \\ 1 & 2 \end{matrix}) are τ = 1 + \sqrt{2} and 1 − \sqrt{2} = −1/τ, that

Q ≤ \frac{τ^{ℓ+3} − (−1/τ)^{ℓ+3}}{τ + 1/τ} ≤ τ^{ℓ+2}.

Now note that, for a given pair of coprime integers (P, Q), at most two tuples (a_{1}, …, a_{ℓ}) ∈ \{1, 2\}^{ℓ} satisfy (3.2). Hence we conclude that there are at least \frac{2^{ℓ}}{2} many distinct pairs of coprime integers (P, Q) such that there exists a tuple (a_{1}, …, a_{ℓ}) ∈ {1, 2}^{ℓ} satisfying (3.2).

Now, let (P, Q) be any such pair of integers, and let (a_{1}, …, a_{ℓ}) be the corresponding tuple. If there are two of them, then choose the smaller one in lexicographic order. Let (T, v) be the tree constructed via Lemma 3.1 and Cor 3.2 such that

r(T, v) = \begin{cases}[a_{1}, …, a_{ℓ}] & if the denominator of [1, a_{1}, …, a_{ℓ}] is odd; \\ [1, a_{1}, …, a_{ℓ}] & if the denominator of [1, a_{1}, …, a_{ℓ}] is even \end{cases} .

It follows that T exists by the recursion in Lemma 3.1 (setting r′ = 1/a_{i} in the i^{th} application of the lemma). By definition of r(T, v) and (3.2), we have P/Q = 1/(1 + r(T, v)). Write r(T, v) = p/q where gcd(p, q) = 1. Then P/Q = q/(p + q) and gcd(q, p + q) = gcd(q, p) = 1, so that

Q = numerator of r(T, v) + denominator of r(T, v) = p + q.

This implies that

(3.3)  i(T) = a(T, v) + b(T, v) = g(T, v)p + g(T, v)q = g(T, v)Q.

It follows from the definition of \overline{S} that g(T, v) is a power of 2, and Lemma 3.3 implies that

g(T, v) ≤ q ≤ Q.

Hence we have, by definition of ℓ,

i(T) = g(T, v)Q ≤ Q^{2} ≤ τ^{2ℓ+4} ≤ N/2 < N.

Now let T′ be the tree obtained from T by adding a vertex v′ that is adjacent to v. By the same argument as before, we have

(3.4)  i(T′) = a(T, v) + 2b(T, v) = g(T, v)p + 2g(T, v)q = g(T, v)P + g(T, v)Q.

Hence we have

i(T′) ≤ 2g(T, v)Q ≤ 2Q^{2} ≤ 2τ^{2ℓ+4} ≤ N.

Now note that we can recover (P, Q) from (i(T), i(T′)), using the following algorithm. First, we can recover the value of Q by taking Q to be the largest odd divisor of i(T). Indeed, this is a consequence of (3.3), together with the facts that Q is odd and g(T, v) is a power of 2. Then, we can recover the value of g(T, v) by taking g(T, v) to be the largest power of 2 dividing i(T). Then, we can recover the value of P by the formula

P = \frac{i(T′) − i(T)}{g(T, v)},

which follows from (3.3) and (3.4).

Combining all the observations above, we conclude that there are at least m := 2^{ℓ}/2 many trees T_{1}, …, T_{m}, such that the vectors (i(T_{j}), i(T′_{j})) (j ∈ [m]) are all distinct, and such that

i(T_{j}) ≤ i(T′_{j}) ≤ N.

So we have m distinct points in {1, …, N}^{2}, and if the distinct x-coordinates appearing are m_{1}, and y-coordinates are m_{2}, then m ≤ m_{1}m_{2}, so m_{i} ≥ \sqrt{m} for at least one i ∈ \{1, 2\}. But m_{1} = |{i(T_{j}), j = 1, …, m}| and m_{2} = |{i(T′_{j}), j = 1, …, m}| and this implies

(3.5)  | I_{tree} ∩\{1, …, N\}| ≥ \sqrt{m}.

Finally, note that by (3.5) and by the definition of ℓ, we have

| I_{tree} ∩\{1, …, N\}| ≥ \sqrt{m} ≥ Ω(N^{(log_{τ} 2)/4}),

for which the theorem follows. □

4. Planar graphs and proof of Theorem 1.5

Theorem 1.5 is a direct consequence of Theorem 2.2 and the following proposition. Here we denote by ϕ := \frac{1+\sqrt{5}}{2} the golden ratio.

Proposition 4.1. For every q ∈ Q_{5}, there exists a connected planar graph G such that q is equal to the number of independent sets in G and |V (G)| ≤ 5 log_{ϕ} q.

Proof. Let q ∈ Q_{5}, and let \frac{p}{q} = [a_{1}, …, a_{ℓ}] be the corresponding continued fraction expansion. Note that a_{1}, …, a_{ℓ} ≤ 5 by definition of Q_{5}. For any a ∈ ℝ, denote

(4.1)  T_{a} := (\begin{matrix}0 & 1 \\ 1 & a \end{matrix}) .

It is easy to see by induction that

(\begin{matrix}∗ & ∗ \\ p & q \end{matrix}) = T_{a_{ℓ}}T_{a_{ℓ−1}} ⋯ T_{a_{1}},

directly associating the matrix product with the continued fraction expansion

\frac{p}{q} = [a_{1}, a_{2}, …, a_{ℓ}].

(Here * denotes entries of the matrix that are ignored.)

A marked planar graph (G, v) is a pair of a connected planar graph G and a marked vertex v of G. Just like with the tree case, let a(G, v) be the number of independent sets of G containing v, and b(G, v) be the number of independent sets not containing v. We denote by Z the set of pairs (a, b) such that there exists a planar marked graph (G, v) with a = a(G, v) and b = b(G, v). Note that (1, 1) ∈ Z, by considering the marked planar graph consisting of a single vertex. Moreover, (1, k) ∈ Z for k = 2 by considering the graph P_{2} (path with 2 vertices, one of which is v), k = 3 using K_{3}, k = 4 using P_{3} with v the middle vertex and k = 5 using the graph P_{3} ∪ {v} connecting every vertex of P_{3} to v (K_{4} minus an edge).

We introduce the following gluing operation on marked graphs. Let (G, v) and (G′, v′) be two marked planar graphs. Suppose further that G′ contains a vertex w′ that is distinct from v′, and both v′ and w′ are adjacent to each other and every other vertex in G′. We define (G′′, v′′) to be the marked graph obtained by taking the disjoint union of G and G′, identifying v with v′, and setting the marked vertex to be v′′ = w′. See Figure 1 for an illustration. Note that G′′ − v′′ is a connected planar graph by construction.

Figure 1. A planar graph obtained by consecutive gluing operations in Proposition 4.1. Each “triangle” is an instance of a G′ graph and the marked vertices are on the bottom line. The corresponding continued fraction is [2, 3, 4, 2, 1, 5, …].

It follows readily that (G′′, v′′) is a marked planar graph satisfying

a(G′′, v′′) = b(G, v), b(G′′, v′′) = a(G, v) + i(G′ − v′ − w′)b(G, v).

Therefore it follows that

if \binom{a}{b} ∈ Z, then T_{k}\binom{a}{b} =^{(4.1)} \binom{b}{a + kb} ∈ Z, (4.2)

where k := i(G′ − v′ − w′). It therefore remains to construct a family of marked planar graphs (G′, v′, w′) satisfying i(G′ − v′ − w′) = k for each k ∈ {1, …, 5}.

Case k ∈ {1, 2, 3}: Let G′ be the complete graph K_{k+1}, and let v′, w′ ∈ V (G′) be any two distinct vertices. Then G′ − v′ − w′ is isomorphic to K_{k−1}, which implies i(G′ − v′ − w′) = k.

Case k = 4: Let G′ be the graph obtained by removing one edge from K_{4}, and let v′, w′ be the two vertices of degree 3. The subgraph G′ − v′ − w′ consists of two isolated vertices, so i(G′ − v′ − w′) = 4.

Case k = 5: Let G′ be the graph H in Figure 2, and let v′ and w′ be any two vertices of degree 4. The subgraph G′ − v′ − w′ is isomorphic to the path graph of 3 vertices, so i(G′ − v′ − w′) = 5.

Figure 2. The graph H for the case k = 5 in Proposition 4.1.

The final constructed graph G starts with a single vertex (corresponding to (1, 1) ∈ Z) and then performs ℓ gluing operations corresponding to k taking the values a_{1}, …, a_{ℓ} in (4.2). Also observe that |V (G′)| ≤ 5 in each of the three cases described above. Since the Euclidean algorithm terminates in at most ℓ ≤ log_{ϕ} q steps for any given q, our construction yields a graph G − v with i(G − v) = q that satisfies the vertex bound |V (G − v)| ≤ 5 log_{ϕ} q. This completes the proof of the proposition. □

5. Graphs with bounded average degree and proof of Theorem 1.7

We split the proof into three parts depending on the average degree d and proving the lower and upper bounds respectively.

5.1. Proof of the lower bound from Theorem 1.7. We will prove the following result.

Lemma 5.1. If d ∈ (0, 2), then there exists a constant c_{1}(d) > 0 such that

| I_{d} ∩ {1, …, N}| ≫ N^{c_{1}(d)}.

Proof. Let N be a sufficiently large integer. Set k := ⌊log_{2} N⌋. It follows from Proposition 4.1 and Theorem 2.2 that, for almost all integers K ∈ {1, …, M} there exists a connected planar graph G := G(K) := (V, E) such that i(G) = K. Let M = N^{\frac{d}{20(6−d)}} . We then have a bound on the number of vertices as

(5.1)  |V | ≤ 5 log_{ϕ} K < 10 log_{2} K ≤ ⌈k/2⌉\frac{d}{6 − d}.

Let G′ be the graph obtained by adding ⌈k/2⌉ isolated vertices into G. Then

i(G′) = 2^{⌈k/2⌉}i(G) = 2^{⌈k/2⌉}K.

Note that the average degree of G′ is given by

d(G′) = \frac{2|E|}{|V | + ⌈k/2⌉} < \frac{6|V |}{|V | + ⌈k/2⌉} ≤ d,

where the first inequality follows from Euler’s formula (i.e., |E| ≤ 3|V | − 6 for connected planar graphs), and the second inequality follows from (5.1). Also note that, by definition of k, K and using d ≤ 2,

i(G′) = 2^{⌈k/2⌉}K ≤ (2\sqrt{N})(N^{\frac{1}{40}} ) < N,

for sufficiently large N. Since the choice of K is arbitrary, the lemma now follows by taking c_{1}(d) := \frac{d}{20(6−d)}. □

5.2. Proof of the upper bound in Theorem 1.7 part (a). The statement would follow from an elementary number theoretic estimate.

Lemma 5.2. Let N be a large integer, let c ∈ (0, 1) and let k ≥ c log_{2}(N). Then the set of integers ≤ N which can be factored as a product of k integers has upper growth exponent < 1, i.e.

|{x ≤ N : x = m_{1} … m_{k} for some m_{i} ≥ 2, m_{i} ∈ ℕ}| ≪ N^{ε}

for any ε ∈ (1 − c, 1).

Proof. Denote the above set by S and let Ω(x) = ∑_{i} a_{i} for x = p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ be the number of prime factors counted with multiplicity. Note that x ∈ S if and only if Ω(x) ≥ k. We use [LP07, Lemma 13], which gives

|S| = ∑_{x≤N, Ω(x)≥k} 1 ≤ \frac{k}{2^{k}} N log N.

We have that k/2^{k} ≤ c log_{2} N/2^{c log_{2} N} = cN^{−c} log_{2} N, so |S| ≤ N^{1−c}(log N)^{2} < N^{ε} asymptotically for every ε ∈ (1 − c, 1). □

We can now prove the relevant portion of Theorem 1.7.

Lemma 5.3. If d ∈ (0, 2), then there exists a constant \frac{1}{2} + \frac{d}{4} < c_{2}(d) < 1 such that

| I_{d} ∩ {1, …, N}| ≪ N^{c_{2}(d)}.

Proof. The idea is that if a graph is sparse then it has many connected components, each contributing a factor in i(G). Let G have n vertices and k connected components G_{1}, …, G_{k} and average degree d. Then since G_{i} is connected we have |E(G_{i})| ≥ n_{i} − 1, so

d ≥ 2\frac{∑_{i} |E(G_{i})|}{∑_{i} n_{i}} ≥ 2\frac{n − k}{n}

and hence k ≥ n(1 − d/2) = d_{1}n for some 0 < d_{1} < 1.

We also have that i(G) = i(G_{1}) ⋯ i(G_{k}) and i(G_{j}) ≥ 2 for each component. Let S′ = {i(G) ≤ N} for graphs G for which k ≥ d_{1}/2 log_{2} N, and let S′′ be the set of numbers of independent sets of graphs with number of connected components < d_{1}/2 log_{2} N.

In the first case we apply Lemma 5.2 since i(G) = i(G_{1}) ⋯ i(G_{k}) and i(G_{j}) ≥ 2 for each component and obtain |S′| ≤ N^{ε} for any ε ∈ (1 − d_{1}/2, 1) = (1/2 + d/4, 1).

In the second case we have d_{1}n ≤ k < d_{1}/2 log_{2} N, so n < \frac{1}{2} log_{2} N. For graphs on n vertices we have i(G) ≤ 2^{n} so i(G) ≤ N^{1/2} and hence |S′′| ≤ N^{1/2}.

Since I_{d} ∩{1, …, N} = S′ ∪ S′′, we get a bound of N^{1/2} + N^{ε} ≪ N^{ε}. We can then set c_{2}(d) = ε ∈ (\frac{1}{2} + \frac{d}{4}, 1). □

5.3. Proof of the completeness part of Theorem 1.7. Here we will show that the numbers of independent sets of graphs with sufficiently large constant average degree can achieve all positive integers.

Lemma 5.4. There exists D > 0 such that if d ≥ D, then I_{d} contains every positive integer.

Proof. It suffices to show that I_{d} contains every prime, since every integer can then be obtained by taking disjoint unions of graphs and this does not increase the average degree.

Let A be the absolute constant from Theorem 2.3. This implies that for any prime q, there exists a positive integer p < q such that p/q = [a_{1}, …, a_{ℓ}] and a_{1}, …, a_{ℓ} ≤ A. Following the same argument as in the proof of Proposition 4.1, it remains to construct a family of marked graphs (G′, v′, w′) satisfying i(G′ − v′ − w′) = k for each k ∈ {1, …, A}. Such a family is easily obtained by taking G′ to be the complete graph K_{k+1}. Note that attaching an additional component G′ = K_{k+1} increases the edge count by \binom{k+1}{2} and the number of vertices by k. Consequently, any graph G produced by this construction satisfies the density bound

d(G) ≤ max_{k∈[A]} \frac{2\binom{k+1}{2}}{k} = A + 1.

The theorem follows by setting D := A + 1. □

6. Final remarks

6.1. Future direction on trees. The constant in Theorem 1.3 (main result for trees) could potentially be improved in a few ways. For example, if one were to believe Hensley’s conjecture [Hen96] (i.e. that the set Q_{2} in Zaremba’s Conjecture contains all but finitely many integers), then the argument in our proof of Theorem 1.3 can be used to show that the lower growth exponent of I_{tree} is at least 1/2. However, showing that the lower density of I_{tree} is positive (which in turn implies that the lower growth exponent is 1) will likely require new arguments.

6.2. Future direction on planar graphs. There are several ways in which one can improve Theorem 1.5 (main result for planar graphs). For example, if one were to believe Zaremba’s Conjecture 2.1, then the argument in our proof of Theorem 1.5 can already be used to resolve Conjecture 1.6 (the planar Linek’s Problem). However, such an approach is likely unnecessarily strong. Indeed, our current method exploits very little of the combinatorial structure of planar graphs. It is entirely possible that a purely combinatorial proof, utilizing larger families of planar graphs, would suffice without relying on deep results from number theory. However, to resolve this problem combinatorially, one needs a better understanding of the possible pairs (a, b) or generalizations of such quantities. Local operations might not be enough.

6.3. Future direction on graphs with bounded average degree. We do not attempt to optimize the constants c_{1}(d) and c_{2}(d) in the first part of Theorem 1.7, as the primary goal of the theorem is simply to bound them away from 0 and 1, respectively. We believe that for d ∈ (0, 2), the growth exponent of I_{d} actually exists, meaning that c_{1}(d) and c_{2}(d) can be chosen to be arbitrarily close to each other. However, proving such a statement appears out of reach with current methods and is secondary to the main focus of this work.

A much more interesting question is whether the second part of Theorem 1.7 can be improved to show that D = 2, thereby resolving Conjecture 1.8. The current constant D is given by D = A + 1, where A is the absolute constant from Theorem 2.3. While A is explicitly computable (see [Shk26, p. 6]), this value is likely far from optimal. As is the case with Theorem 1.5 for planar graphs, our current approach relies on heavy machinery from number theory that is likely unnecessary. Finding a more elementary proof of the current result could pave the way toward a full resolution of the conjecture.

6.4. Connections between inverse enumeration problems and continued fractions. Our approach to studying inverse enumeration problems through the lens of continued fraction theory is inspired by the recent work of Chan–Kontorovich–Pak [CKP24]. That paper introduced this strategy to obtain the first known exponential lower bound for Sedláček’s problem. Specifically, they established that

|T (n)| ≥ (1.1103)^{n},

where T (n) is the set of integers that can be realized as the number of spanning trees of a simple connected graph on n vertices. The current best lower bound in the literature is (1.55)^{n}, due to Alon, Bucić, and Gishboliner [ABG25], who also provide a simplified proof.

Another work on inverse enumeration problems that uses similar techniques is the recent work of Chan–Kontorovich–Pak [CKP25], which employed Bourgain’s results [Bou12] on the sum of continued fractions to achieve the optimal bound for the inverse effective resistance problem. Finally, we also note the work of Agol and Krushkal [AK19] on the exponential lower bound for the inverse chromatic polynomial problem, as well as the recent follow-up by Miyazaki, Pohoata, and Zheng [MPZ25], which strengthens the Agol–Krushkal result by unifying their approach with ideas from Alon–Bucić–Gishboliner [ABG25].

6.5. Independence polynomials of trees. The number of independent sets of trees can be refined via their independence polynomial

I_{G}(x) = ∑_{k=0}^{n} i_{k}(G)x^{k},

where i_{k}(G) is the number of independent sets of size k in G. A conjecture of Alavi–Malde– Schwenk–Erdős from 1987 [AMSE87] states that the sequence {i_{k}(T)}_{k} is unimodal when the graph is a tree. Many partial results have provided further evidence towards this conjecture, while also disproving the stronger log-concavity property. The literature on this topic is vast, see some of the most recent developments in [BBP25, Hei25, Gal25, RS25] and references therein. While we study the inverse problem of finding which integers are equal to I_{T} (1), it would be a much more challenging question to characterize the independence sequences {i_{k}(T)}_{k}.

6.6. Caterpillars. A special class of trees, also of great relevance to §6.5, are the caterpillar trees which consist of a spine of vertices v_{1}, v_{2}, …, v_{k} with (v_{i}, v_{i+1}) ∈ E and “cherries” of leaves connected to each vertex, so vertex v_{i} has a_{i} many leaves connected to it. It is not very hard to see that the trees constructed in Section 3 are actually from that class. Computational results show that the numbers of independent sets of caterpillars already cover close to 1/2 of the integers in large enough intervals and we conjecture that this is indeed the case.

6.7. Vertex minimality. A related problem concerns optimizing with respect to the number of vertices. In particular, what is the smallest number of vertices v = v(N) needed to construct a graph with number of independent sets N. For instance, [CP24, Ex. 5.8] demonstrates a construction where log_{2} N ≤ v(N) ≤ 2 log_{2}(N + 1). If we assume that trees achieve all but finitely many numbers (Conjecture 1.2), it is then easy to see N ≥ F_{v(N)+2}, so v(N) ≤ log_{ϕ} N (i.e. a multiplicative constant improvement for the upper bound). We can then ask: for a given N, what is the asymptotic behavior of the ratio \frac{log v(N)}{log N}?

Acknowledgement

We thank Lior Gishboliner, Alex Kontorovich, and Cosmin Pohoata for stimulating discussions on these problems and Noga Alon and Igor Rivin for interesting questions and directions. The first author would like to thank the National University of Singapore for their warm hospitality during his sabbatical in Spring 2026.

7. Appendix: Forbidden Integers

Here is a list of the 823 known integers that cannot be equal to the number of independent sets of a tree.

4 6 7 10 11 12 15 16 18 19 20 25 27 28 29 30 31 32 39 42 45 46 47 48 49 51 52 53 54 56 63 67 71 72 73 74 75 78 79 81 82 85 86 87 88 90 91 103 111 115 117 119 123 125 127 130 131 132 135 136 137 138 139 140 141 142 143 146 147 151 155 177 179 185 191 193 201 203 205 207 208 210 211 213 214 215 219 220 221 223 227 228 229 230 231 235 237 238 239 240 244 247 251 265 271 291 295 299 301 303 315 322 325 329 331 333 337 339 341 343 345 347 350 355 357 358 359 361 362 363 369 373 374 379 385 387 389 391 399 400 407 413 427 437 455 463 467 475 477 481 483 487 497 507 509 515 519 521 529 535 539 541 543 551 555 559 561 563 567 573 575 577 579 583 585 591 593 594 605 607 609 611 621 622 623 625 626 627 628 629 633 639 641 645 646 647 656 677 683 699 703 709 719 721 759 787 797 805 813 827 837 839 847 851 855 859 869 871 875 883 887 891 897 901 907 911 913 915 921 923 925 927 933 935 937 939 943 949 953 955 961 963 967 969 971 973 975 977 979 989 991 993 995 999 1001 1003 1007 1009 1013 1015 1017 1018 1019 1023 1031 1041 1043 1045 1047 1063 1069 1081 1083 1095 1103 1111 1117 1123 1129 1159 1171 1179 1189 1235 1247 1281 1287 1333 1339 1363 1383 1385 1389 1397 1439 1441 1459 1461 1463 1469 1477 1493 1513 1517 1519 1523 1525 1526 1527 1531 1539 1541 1553 1567 1569 1571 1573 1581 1595 1598 1603 1605 1615 1623 1625 1631 1635 1639 1642 1643 1647 1651 1655 1657 1667 1671 1679 1685 1687 1691 1703 1711 1723 1729 1747 1751 1759 1763 1767 1771 1791 1793 1817 1823 1829 1871 1923 1931 1937 2081 2111 2119 2171 2179 2195 2209 2237 2239 2249 2269 2287 2291 2299 2353 2355 2359 2369 2377 2379 2381 2399 2403 2411 2427 2451 2457 2471 2481 2485 2491 2497 2499 2513 2515 2517 2519 2539 2549 2555 2567 2569 2571 2577 2593 2597 2599 2605 2611 2619 2621 2625 2633 2639 2643 2653 2657 2667 2677 2685 2713 2715 2721 2731 2737 2743 2755 2758 2761 2771 2811 2815 2821 2831 2835 2839 2841 2861 2863 2921 2933 2941 2951 2975 2989 3061 3113 3119 3137 3259 3287 3371 3389 3403 3409 3439 3515 3535 3601 3613 3619 3635 3647 3679 3763 3775 3791 3831 3847 3867 3871 3895 3913 3923 3927 3931 3935 3955 3967 3979 3983 3985 3991 4013 4039 4043 4049 4063 4067 4069 4081 4095 4103 4107 4111 4113 4119 4139 4151 4165 4175 4177 4189 4195 4199 4203 4207 4209 4229 4233 4259 4263 4287 4303 4305 4331 4337 4367 4375 4379 4411 4417 4431 4433 4435 4451 4465 4475 4487 4519 4521 4522 4529 4547 4555 4561 4565 4579 4603 4607 4619 4657 4667 4675 4691 4727 4739 4741 4787 4795 4803 4811 4867 4907 4981 4997 5011 5033 5041 5099 5173 5227 5417 5423 5581 5591 5603 5611 5653 5719 5725 5821 5885 5939 5993 5997 5999 6167 6171 6223 6301 6313 6323 6451 6477 6491 6499 6539 6563 6575 6577 6607 6617 6627 6653 6727 6739 6751 6755 6757 6803 6827 6901 6929 6941 6947 6973 6977 6983 7049 7055 7059 7067 7117 7169 7175 7193 7203 7211 7265 7279 7343 7357 7369 7371 7379 7385 7401 7419 7431 7441 7451 7457 7459 7463 7489 7517 7559 7619 7649 7679 7733 7769 7775 7811 7817 7819 7847 7927 7987 8041 8047 8057 8059 8107 8117 8167 8261 8393 8399 8461 8467 8831 9023 9089 9131 9181 9463 9581 9611 9647 9691 9767 9811 9863 9883 10037 10079 10093 10127 10293 10399 10581 10733 10747 10751 10775 10789 10999 11027 11029 11167 11183 11257 11353 11413 11425 11443 11503 11543 11603 11639 11669 11671 11759 11769 11793 11827 11969 11989 12019 12079 12089 12121 12131 12323 12329 12517 12547 12565 12583 12639 12749 12931 12953 12979 12989 13015 13051 13099 13111 13139 13199 13291 13363 13501 13513 13607 13643 13807 13879 14483 14993 15329 16643 16693 16751 16879 17131 17183 17233 17427 17471 17507 17571 17759 17837 18221 18275 18383 18389 18667 18679 18893 18899 18943 19139 19207 19265 19333 19477 19481 19565 19765 19939 20009 20373 20387 20447 20537 20543 20659 21223 21419 21527 21989 22183 22453 24101 24239 24433 25499 26167 26219 26719 27167 27527 29371 29537 29639 30319 30471 30821 31493 31997 32699 32767 32857 32873 33031 33073 34139 34483 34789 34909 36619 37027 43039 45983 47401 48917 49253 55487 88013

References

[ABG25] Noga Alon, Matija Bucić, and Lior Gishboliner, The spanning tree spectrum: improved bounds and simple proofs, 2025, preprint, 9 pp., arXiv:2503.23648, to appear in Proceedings of the American Mathematical Society.

[AHK11] Noga Alon, Simi Haber, and Michael Krivelevich, The number of f-matchings in almost every tree is a zero residue, The Electronic Journal of Combinatorics 18 (2011), P30, 10 pp.

[AK19] Ian Agol and Vyacheslav Krushkal, Structure of the flow and Yamada polynomials of cubic graphs, Breadth in contemporary topology, Proceedings of Symposia in Pure Mathematics, vol. 102, Amer. Math. Soc., Providence, RI, 2019, pp. 1—20.

[AMSE87] Yousef Alavi, Paresh J. Malde, Allen J. Schwenk, and Paul Erdős, The vertex independence sequence of a graph is not constrained, Congressus Numerantium 58 (1987), 15–23.

[BBP25] Ferenc Bencs, Pjotr Buys, and Han Peters, The limit of the zero locus of the independence polynomial for bounded degree graphs, Michigan Mathematical Journal 75 (2025), no. 2, 423–448.

[BK14] Jean Bourgain and Alex Kontorovich, On Zaremba’s conjecture, Annals of Mathematics 180 (2014), no. 1, 137–196.

[Bou12] Jean Bourgain, Partial quotients and representation of rational numbers, Comptes Rendus Mathematique 350 (2012), 727–730.

[CKP24] Swee Hong Chan, Alex Kontorovich, and Igor Pak, Spanning trees and continued fractions, 2024, preprint, 21 pp., arXiv:2411.18782.

[CKP25] , Effective resistance in planar graphs and continued fractions, 2025, preprint, 10 pp., arXiv:2505.19168.

[CP24] Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, Theoretical Computer Science 1015 (2024), no. 114776, 19 pp.

[DK25] Ewan Davies and Ross J. Kang, The hard-core model in graph theory, 2025, preprint, 35 pp., arXiv:2501.03379.

[Gal25] David Galvin, Trees with non log-concave independent set sequences, 2025, preprint, 10 pp., arXiv:2502.10654.

[Gre00] Catherine Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs, Computational Complexity 9 (2000), no. 1, 52–72.

[Hei25] Steven Heilman, Independent sets of random trees and sparse random graphs, Journal of Graph Theory 109 (2025), no. 3, 294–309.

[Hen96] Doug Hensley, A polynomial time algorithm for the Hausdorff dimension of continued fraction Cantor sets, Journal of Number Theory 58 (1996), no. 1, 9–45.

[HHK^{+}25] Michael Han, Sycamore Herlihy, Kirsti Kuenzel, Daniel Martin, and Rachel Schmidt, The number of independent sets in bipartite graphs and benzenoids, Aequationes Mathematicae 99 (2025), 1175–1195.

[Hua15] Shin Yih Huang, An improvement to Zaremba’s conjecture, Geometric and Functional Analysis 25 (2015), 860–914.

[Law10] Hiu-Fai Law, On the number of independent sets in a tree, The Electronic Journal of Combinatorics 17 (2010), N18, 5 pp.

[Law12] , On the number of f-matchings in a tree, The Electronic Journal of Combinatorics 19 (2012), P43, 11 pp.

[Lin89] Václav Linek, Bipartite graphs can have any number of independent sets, Discrete Mathematics 76 (1989), no. 2, 131–136.

[LP07] Florian Luca and Carl Pomerance, Irreducible radical extensions and euler-function chains, Integers 7 (2007), no. 2, A25, 11 pp.

[MPZ25] Rafael Miyazaki, Cosmin Pohoata, and Michael Zheng, Chromatic polynomial evaluation spectra, 2025, preprint, 20 pp., arXiv:2512.19600.

[RS25] Eric Ramos and Sunny Sun, An AI enhanced approach to the tree unimodality conjecture, 2025, preprint, 35 pp., arXiv:2510.18826.

[Shk26] Ilya D. Shkredov, On some results of Korobov and Larcher and Zaremba’s conjecture, 2026, preprint, 36 pp., arXiv:2603.14116.

[Sly10] Allan Sly, Computational transition at the uniqueness threshold, Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 287–296.

[Wag09] Stephan G. Wagner, Almost all trees have an even number of independent sets, The Electronic Journal of Combinatorics 16 (2009), no. 1, R93, 10 pp.

[Wei06] Dror Weitz, Counting independent sets up to the tree threshold, Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 140–149.

[Zar72] Stanisław K. Zaremba, La méthode des “bons treillis” pour le calcul des intégrales multiples, Applications of number theory to numerical analysis, Academic Press, New York-London, 1972, pp. 39–119.