3 \((k,\ell )\)-sparsity and \((k,\ell )\)-tightness
Throughout this section \(k\) and \(\ell \) are non-negative integers. We define \((k,\ell )\)-sparse and \((k,\ell )\)-tight graphs, as Lee and Streinu [ LS08 ] do for multigraphs, and \((k,\ell )\)-tight sets of vertices. The Laman graphs of section 4 are the case \((k,\ell ) = (2,3)\), which Jordán’s survey [ Jor16 ] treats in §2.1.
After the definitions we show that sparsity passes to subgraphs and bounds the number of edges. Two facts about \((2,3)\)-sparse graphs follow: such a graph has a vertex of degree at most three, and no vertex has three pairwise adjacent neighbours. Sparsity and tightness are invariant under isomorphism. The main result is that two tight sets in a sparse graph have a tight union and a tight intersection if their intersection is large enough (theorem 3.14). Two variants enlarge a tight set by counting edges that it does not span. Next comes a counting lemma for reversing the Type II Henneberg move (definition 5.2), that is, for deleting a vertex of degree three and joining two of its neighbours by an edge. The section ends with the reverse decomposition of a \((2,3)\)-sparse graph with an edge: it has a vertex whose deletion leaves a \((2,3)\)-sparse graph, after such an edge is added if the vertex has degree three (theorem 3.19).
3.1 Definitions
\(G\) is \((k,\ell )\)-sparse if every finite set \(s \subseteq V\) with \(\ell \le k\, |s|\) spans at most \(k\, |s| - \ell \) edges, that is,
The formal definition states the bound in the additive form displayed above. Edge counts there are natural numbers, in which \(k\, |s| - \ell \) would be truncated at \(0\). Under the hypothesis \(\ell \le k\, |s|\) the two forms agree.
Let \(V\) be finite. The graph \(G\) is \((k,\ell )\)-tight if it is \((k,\ell )\)-sparse and
A finite set \(s \subseteq V\) is \((k,\ell )\)-tight in \(G\) if it attains the sparsity bound:
Tightness of a set is the local form of tightness of the graph. Since \(E_{G}[V] = E(G)\) (lemma 2.3), a \((k,\ell )\)-sparse graph \(G\) on a finite set \(V\) is \((k,\ell )\)-tight exactly when \(V\) is a \((k,\ell )\)-tight set in \(G\). At \((k,\ell ) = (2,3)\) the hypothesis \(\ell \le k\, |s|\) of definition 3.1 says that \(|s| \ge 2\). So a finite simple graph is \((2,3)\)-sparse exactly when it is sparse in the sense of Jordán [ Jor16 ] §2.1, and its \((2,3)\)-tight sets are what he calls critical sets. We use “tight” throughout.
3.2 Basic properties and the global edge bound
Sparsity passes to subgraphs. Applied to the whole vertex set, it bounds the number of edges of \(G\), so that a tight graph has as many edges as a sparse graph on \(V\) can have.
Let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\). If \(G'\) is \((k,\ell )\)-sparse, then so is \(G\).
For a finite set \(s \subseteq V\), every edge of \(G\) with both endpoints in \(s\) is an edge of \(G'\) with both endpoints in \(s\), so \(|E_{G}[s]| \le |E_{G'}[s]|\). The sparsity bound for \(G'\) at \(s\) therefore bounds \(|E_{G}[s]|\).
Let \(V\) be finite, and let \(G\) be \((k,\ell )\)-sparse with \(\ell \le k\, |V|\). Then
Apply the sparsity bound at \(s = V\) and use \(E_{G}[V] = E(G)\) (lemma 2.3).
Let \(V\) be finite, let \(G\) be \((k,\ell )\)-tight, and let \(H\) be a graph on \(V\) with \(E(G) \subsetneq E(H)\). Then \(H\) is not \((k,\ell )\)-sparse.
By tightness \(|E(G)| + \ell = k\, |V|\); in particular \(\ell \le k\, |V|\). Since \(E(G)\) is a proper subset of \(E(H)\), we have \(|E(G)| {\lt} |E(H)|\), and so \(|E(H)| + \ell {\gt} k\, |V|\). By lemma 3.6, \(H\) is not \((k,\ell )\)-sparse.
3.3 Low-degree vertex and non-adjacency consequences
Both lemmas below concern \((2,3)\)-sparse graphs. The first is applied to Laman graphs in lemma 4.6. The second is used in the reverse decomposition of a \((2,3)\)-sparse graph, at a vertex of degree three (theorem 3.19).
Let \(V\) be finite with \(|V| \ge 2\), and let \(G\) be \((2,3)\)-sparse. Then some vertex of \(G\) has degree at most \(3\).
Suppose that every vertex has degree at least \(4\). By the handshake identity, \(2|E(G)| = \sum _v \deg _G(v) \ge 4|V|\). The global edge bound (lemma 3.6) applies at \((k, \ell ) = (2, 3)\), since \(3 \le 2|V|\) when \(|V| \ge 2\). It gives \(|E(G)| + 3 \le 2|V|\), so \(2|E(G)| \le 4|V| - 6 {\lt} 4|V|\), a contradiction.
Let \(V\) be finite and let \(G\) be \((2,3)\)-sparse. Suppose that \(v \in V\) has three pairwise distinct neighbors \(a, b, c\). Then at least one of the pairs \(\{ a, b\} \), \(\{ a, c\} \), \(\{ b, c\} \) is non-adjacent in \(G\).
Suppose that all three pairs are adjacent, and let \(X = \{ v, a, b, c\} \). The vertices \(a\), \(b\) and \(c\) are distinct, and each differs from \(v\) because \(G\) has no loops, so \(|X| = 4\). The set \(X\) spans the six distinct edges \(va\), \(vb\), \(vc\), \(ab\), \(ac\) and \(bc\), so \(|E_{G}[X]| \ge 6\). But \((2,3)\)-sparsity applies at \(X\), since \(3 \le 2 \cdot 4\), and gives \(|E_{G}[X]| \le 2 \cdot 4 - 3 = 5\), a contradiction.
3.4 Invariance under isomorphism
Invariance under isomorphism is evident for properties defined by counting edges. We record it because a Henneberg move (section 5) produces a graph on a new vertex set, which is identified with a given graph only up to isomorphism.
Let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\), and let \(s \subseteq V\). Then
where \(\varphi \) maps a pair \(\{ u, v\} \) of vertices to \(\{ \varphi (u), \varphi (v)\} \).
Since \(\varphi \) preserves adjacency in both directions, a pair \(\{ p, q\} \) is an edge of \(G\) inside \(s\) if and only if \(\{ \varphi (p), \varphi (q)\} \) is an edge of \(H\) inside \(\varphi (s)\). Every pair of vertices of \(H\) inside \(\varphi (s)\) is of this form.
Let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\). If \(G\) is \((k,\ell )\)-sparse, then so is \(H\).
Let \(s\) be a finite set of vertices of \(H\) with \(\ell \le k\, |s|\), and let \(s' = \varphi ^{-1}(s)\), so that \(|s'| = |s|\). The map on pairs induced by \(\varphi \) is injective, and it maps \(E_{G}[s']\) onto \(E_{H}[s]\) (lemma 3.10). So \(|E_{H}[s]| = |E_{G}[s']|\), and the sparsity bound for \(G\) at \(s'\) is the bound for \(H\) at \(s\).
Let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\). If \(G\) is \((k,\ell )\)-tight, then so is \(H\).
The graph \(H\) is \((k,\ell )\)-sparse by lemma 3.11. The isomorphism is a bijection between the vertex sets of \(G\) and \(H\), and it induces a bijection from \(E(G)\) to \(E(H)\). So \(G\) and \(H\) have the same numbers of vertices and of edges, and the equation \(|E(G)| + \ell = k\, |V|\) gives the same equation for \(H\).
3.5 Unions and intersections of tight sets
Each proof in this subsection shows that a set spans at least as many edges as tightness requires. The sparsity bound gives the reverse inequality, so the bound is attained. The first lemma records this step.
Let \(G\) be \((k,\ell )\)-sparse, and let \(s \subseteq V\) be a finite set with \(\ell \le k\, |s|\) and
Then \(s\) is \((k,\ell )\)-tight in \(G\).
Sparsity at \(s\) gives \(|E_{G}[s]| + \ell \le k\, |s|\), so equality holds.
At \((k,\ell ) = (2,3)\) the size hypothesis of the next theorem says that \(|s \cap t| \ge 2\), and the theorem is the part of Jordán’s Lemma 2.1.2 [ Jor16 ] that concerns critical sets. For general \(k\) and \(\ell {\lt} 2k\), see Lee and Streinu [ LS08 , Theorem 5(1) ] , who call the subgraph induced on a tight set a block.
Let \(V\) be finite and let \(G\) be \((k,\ell )\)-sparse. Let \(s, t \subseteq V\) be \((k,\ell )\)-tight in \(G\), and suppose that \(\ell \le k\, |s \cap t|\). Then \(s \cup t\) and \(s \cap t\) are \((k,\ell )\)-tight in \(G\).
Since \(|s \cup t| \ge |s \cap t|\), the hypothesis \(\ell \le k\, |s \cap t|\) lets us apply sparsity at \(s \cap t\) and at \(s \cup t\):
Adding these and using \(|s \cup t| + |s \cap t| = |s| + |t|\) gives
On the other hand, \(s\) and \(t\) are tight, and supermodularity (lemma 2.8) gives
So the sum of the two sparsity inequalities above is an equality. Hence each of them is an equality, that is, \(s \cup t\) and \(s \cap t\) are tight.
The next two results need no size hypothesis. The first combines two tight sets \(s_1\) and \(s_2\) and counts edges that join \(s_1 \setminus s_2\) to \(s_2 \setminus s_1\), which are the edges that the inequality of lemma 2.8 leaves out. Without such edges, and under the size hypothesis of theorem 3.14, it gives the union half of that theorem. The second adds a vertex to a tight set together with \(k\) edges joining it to the set. The reverse decomposition of a \((2,3)\)-sparse graph at a vertex of degree three uses both (theorem 3.19).
Let \(V\) be finite, let \(G\) be \((k,\ell )\)-sparse, and let \(s_1, s_2 \subseteq V\) be \((k,\ell )\)-tight in \(G\). Let \(F\) be a set of edges of \(G\) inside \(s_1 \cup s_2\) that lie in neither \(E_{G}[s_1]\) nor \(E_{G}[s_2]\), and suppose that
Then \(s_1 \cup s_2\) is \((k,\ell )\)-tight in \(G\).
The sets \(E_{G}[s_1]\), \(E_{G}[s_2]\) and \(F\) lie in \(E_{G}[s_1 \cup s_2]\) (lemma 2.2), and \(F\) is disjoint from the other two. Their intersection is \(E_{G}[s_1] \cap E_{G}[s_2] = E_{G}[s_1 \cap s_2]\) (lemma 2.7). Counting their union as in the proof of lemma 2.8 gives
Since \(s_1\) and \(s_2\) are tight, the left side equals \(k\, |s_1| + k\, |s_2| - 2\ell + |F|\). We substitute \(|s_1| + |s_2| = |s_1 \cup s_2| + |s_1 \cap s_2|\) and bound \(|E_{G}[s_1 \cap s_2]|\) by the hypothesis on \(F\). This gives
Tightness of \(s_1\) also gives \(\ell \le k\, |s_1| \le k\, |s_1 \cup s_2|\). So \(s_1 \cup s_2\) is tight by lemma 3.13.
Let \(G\) be \((k,\ell )\)-sparse, and let \(s \subseteq V\) be \((k,\ell )\)-tight in \(G\). Let \(w \in V \setminus s\), and let \(F\) be a set of at least \(k\) edges of \(G\) inside \(s \cup \{ w\} \) that are not in \(E_{G}[s]\). Then \(s \cup \{ w\} \) is \((k,\ell )\)-tight in \(G\).
The sets \(E_{G}[s]\) and \(F\) are disjoint, and both lie in \(E_{G}[s \cup \{ w\} ]\) (lemma 2.2). Since \(s\) is tight and \(w \notin s\),
Tightness of \(s\) also gives \(\ell \le k\, |s| \le k\, |s \cup \{ w\} |\). So \(s \cup \{ w\} \) is tight by lemma 3.13.
3.6 Splittings and tight sets
Let \(v\) be a vertex of degree three with neighbours \(x\), \(y\) and \(z\), where \(x\) and \(y\) are not adjacent. Deleting \(v\) and joining \(x\) to \(y\) by an edge reverses the Type II move on \(xy\) and \(z\) (definition 5.2). Jordán [ Jor16 ] calls this operation splitting \(v\) on the pair \(vx\), \(vy\), and calls the splitting suitable if the resulting graph is sparse (§2.1, p. 44). His proof of Lemma 2.1.4(b) begins with an observation about a sparse graph: if a splitting is not suitable, then some critical set, that is, some \((2,3)\)-tight set, contains \(x\) and \(y\) but not \(v\). We prove this for any vertex \(v\) and any vertices \(x, y \ne v\), since the count does not use the degree of \(v\).
Let \(V\) be finite, let \(G\) be \((2,3)\)-sparse, and let \(v\), \(x\) and \(y\) be vertices of \(G\) with \(x, y \ne v\). Let \(G - v + xy\) be the graph on \(V \setminus \{ v\} \) obtained from \(G\) by deleting \(v\) and adding the edge \(xy\). If \(G - v + xy\) is not \((2,3)\)-sparse, then some set \(S \subseteq V \setminus \{ v\} \) that contains \(x\) and \(y\) is \((2,3)\)-tight in \(G\).
Since \(G - v + xy\) is not \((2,3)\)-sparse, some finite set \(S \subseteq V \setminus \{ v\} \) with \(|S| \ge 2\) spans more than \(2|S| - 3\) edges of \(G - v + xy\). As \(v \notin S\), these edges are the edges of \(G\) inside \(S\), together with \(xy\) if both \(x\) and \(y\) lie in \(S\).
If \(x \notin S\) or \(y \notin S\), then \(S\) spans the same edges in \(G - v + xy\) as in \(G\), and this contradicts the sparsity of \(G\). So \(x, y \in S\), and \(S\) spans at most one more edge in \(G - v + xy\) than in \(G\). Hence \(|E_{G}[S]| + 1 {\gt} 2|S| - 3\), that is, \(2|S| \le |E_{G}[S]| + 3\). By lemma 3.13, \(S\) is \((2,3)\)-tight in \(G\).
The formal statement does not build \(G - v + xy\) on the subset \(V \setminus \{ v\} \) of \(V\). Its vertex set is a separate copy of \(V \setminus \{ v\} \), which the inclusion map sends into \(V\). Two of its vertices are adjacent if their images are adjacent in \(G\) or are \(x\) and \(y\). The proof therefore first maps the violating set into \(V\). The inclusion is injective, so the image has as many vertices as the set, and the edges of \(G\) inside the image correspond one to one to the edges of \(G - v\) inside the set. The reverse decompositions theorem 3.19 and theorem 5.12 build \(G - v\) and \(G - v + xy\) in the same way.
3.7 Sparse-graph reverse decomposition
Below is the reverse decomposition of Laman graphs (section 5.4) in its form for \((2,3)\)-sparse graphs, where the vertex may also have degree one. The induction of section 10.2 removes the vertex that the theorem gives at each step. We write \(G - v\) for the graph obtained from \(G\) by deleting a vertex \(v\), and \(G - v + ab\) for the graph obtained from \(G - v\) by adding the edge \(ab\), as in lemma 3.17.
Jordán [ Jor16 ] finds a vertex of degree one, two or three in his proof of Theorem 2.2.1 (p. 45). He proves the cases of degree two and three as his Lemma 2.1.4 (p. 44): if \(v\) has degree two, then \(G - v\) is sparse, and if \(v\) has degree three, then \(v\) has a suitable splitting (section 3.6). His proof of the second part uses two facts about critical sets, which are our \((2,3)\)-tight sets. The first is his Lemma 2.1.2, and the part of it that we use is theorem 3.14 at \((k,\ell ) = (2,3)\). The second is his Lemma 2.1.3, which says in part that if three tight sets meet pairwise in exactly one vertex and have no vertex in common, then their union is tight. We prove the case of Lemma 2.1.3 that we need within the proof of the theorem.
Let \(V\) be finite, and let \(G\) be a \((2,3)\)-sparse graph on \(V\) with at least one edge. Then \(G\) has a vertex \(v\) for which one of the following holds.
The vertex \(v\) has degree one, with neighbour \(a\), and \(G - v\) is \((2,3)\)-sparse.
The vertex \(v\) has degree two, with neighbours \(a\) and \(b\), and \(G - v\) is \((2,3)\)-sparse.
The vertex \(v\) has degree three, with neighbours \(a\), \(b\) and \(c\), where \(a\) and \(b\) are not adjacent, and \(G - v + ab\) is \((2,3)\)-sparse.
Here \(G - v\) is the graph on \(V \setminus \{ v\} \) obtained from \(G\) by deleting \(v\), and \(G - v + ab\) is obtained from \(G - v\) by adding the edge \(ab\).
We find \(v\) by the argument of lemma 3.8, applied to the vertices of positive degree. Let \(U\) be the set of these vertices. Every edge of \(G\) has both ends in \(U\). So \(U\) spans every edge of \(G\), and \(|U| \ge 2\), since \(G\) has an edge. Sparsity at \(U\) gives \(|E(G)| + 3 \le 2|U|\). If every vertex in \(U\) had degree at least four, the handshake identity would give \(2|E(G)| = \sum _{u \in U} \deg _G(u) \ge 4|U|\), a contradiction. So some vertex \(v\) has degree one, two or three (IsSparse.exists_one_le_degree_le_three).
If \(v\) has degree one or two, then a set of vertices of \(G - v\) spans the same edges in \(G - v\) as in \(G\), so \(G - v\) is \((2,3)\)-sparse. For degree two this is Jordán’s Lemma 2.1.4(a).
Let \(v\) have degree three, with neighbours \(a\), \(b\) and \(c\). We must show that \(v\) has a suitable splitting, that is, two neighbours \(x\) and \(y\) that are not adjacent and for which \(G - v + xy\) is \((2,3)\)-sparse. Suppose that it has none. We use an observation from Jordán’s proof: no \((2,3)\)-tight set \(T\) with \(v \notin T\) contains all three neighbours of \(v\) (IsSparse.no_isTightOn_excluding_three_neighbors). Otherwise \(T \cup \{ v\} \) spans the edges inside \(T\) and the edges \(va\), \(vb\) and \(vc\), so that
against sparsity. We derive a contradiction by constructing such a set \(T\).
If two neighbours of \(v\) are not adjacent, the splitting of \(v\) on them is not suitable, so some tight set that does not contain \(v\) contains both of them (lemma 3.17). At least one pair of neighbours of \(v\) is not adjacent (lemma 3.9). Jordán’s proof takes such a tight set for each of the three pairs; for an adjacent pair, the pair itself is such a set. We follow the formal proof instead, which distinguishes how many pairs are not adjacent (IsSparse.False_of_pairwise_blocker_or_edge).
Suppose first that exactly one pair is not adjacent, say \(a\) and \(b\) (IsSparse.contradiction_one_pair). Let \(S\) be a tight set with \(a, b \in S\) and \(v \notin S\). If \(c \in S\), let \(T = S\). Otherwise the edges \(ca\) and \(cb\) join \(c\) to \(S\), and \(T = S \cup \{ c\} \) is tight by theorem 3.16 with \(k = 2\).
Suppose next that exactly two pairs are not adjacent, say \(a, c\) and \(b, c\), so that \(ab\) is an edge (IsSparse.contradiction_two_pair). Let \(S_1\) and \(S_2\) be tight sets that do not contain \(v\), with \(a, c \in S_1\) and \(b, c \in S_2\), and let \(T = S_1 \cup S_2\). If \(|S_1 \cap S_2| \ge 2\), then \(T\) is tight by theorem 3.14. Otherwise \(S_1 \cap S_2 = \{ c\} \), so \(a \notin S_2\) and \(b \notin S_1\). Then the edge \(ab\) lies inside \(T\) but in neither \(E_{G}[S_1]\) nor \(E_{G}[S_2]\). So theorem 3.15 applies with \(F = \{ ab\} \), where its hypothesis reads \(0 + 3 \le 2 \cdot 1 + 1\), and \(T\) is tight.
Suppose finally that no two of \(a\), \(b\) and \(c\) are adjacent (IsSparse.contradiction_three_pair). Let \(S_{ab}\), \(S_{ac}\) and \(S_{bc}\) be tight sets that do not contain \(v\), each containing the two vertices in its index. If two of them meet in at least two vertices, then their union contains \(a\), \(b\) and \(c\), and it is tight by theorem 3.14; let \(T\) be this union. Otherwise
This is the configuration of Jordán’s Lemma 2.1.3. We show that \(T = S_{ab} \cup S_{ac} \cup S_{bc}\) is tight by applying supermodularity (lemma 2.8) twice. The set \(S_{ab} \cap S_{ac} = \{ a\} \) spans no edge, so
The set \((S_{ab} \cup S_{ac}) \cap S_{bc} = \{ b, c\} \) spans no edge either, since \(b\) and \(c\) are not adjacent, so
The three sets are tight, and \(|T| = |S_{ab}| + |S_{ac}| + |S_{bc}| - 3\). Hence
and \(T\) is tight by lemma 3.13.
In each case \(T\) is a tight set that contains \(a\), \(b\) and \(c\) but not \(v\), which is impossible. So \(v\) has a suitable splitting.