2 Edges in a vertex set
Laman graphs are defined by counting edges: a graph on \(n \ge 2\) vertices is a Laman graph if it has \(2n - 3\) edges and every set of \(m \ge 2\) of its vertices spans at most \(2m - 3\) of them. This section and the next develop this counting with general constants \(k\) and \(\ell \) in place of \(2\) and \(3\), and section 4 returns to Laman graphs. Throughout both sections, \(G\) is a simple graph on a vertex set \(V\), which we assume to be finite only where a statement says so.
This section studies the set of edges of \(G\) with both endpoints in a given vertex set. We show that this set grows with the vertex set and compute it at a few small sets. We then count the edges that remain when a vertex is deleted, and finally compare the counts at two vertex sets with the counts at their union and intersection. Section 3 defines \((k,\ell )\)-sparse and \((k,\ell )\)-tight graphs and develops their basic theory.
2.1 Definition and basic properties
For \(S \subseteq V\), let
be the set of edges of \(G\) with both endpoints in \(S\), that is, the edge set of the subgraph of \(G\) induced on \(S\). We say that \(S\) spans these edges.
Let \(S \subseteq T \subseteq V\). Then \(E_{G}[S] \subseteq E_{G}[T]\).
An edge \(e \subseteq S\) also satisfies \(e \subseteq T\).
Let \(v \in V\) and \(S \subseteq V\). Then \(E_{G}[V] = E(G)\), \(E_{G}[\emptyset ] = \emptyset \) and \(E_{G}[\{ v\} ] = \emptyset \). If \(G\) has no edges, then \(E_{G}[S] = \emptyset \).
All but the third are immediate from the definition. A singleton \(\{ v\} \) contains no edge, since \(G\) has no loops and so the two endpoints of an edge are distinct.
The four pins are the four claims, in the order stated.
2.2 Vertex deletion
Let \(v \in V\), and write \(\{ v\} ^c = V \setminus \{ v\} \). The set \(E_{G}[\{ v\} ^c]\) consists of the edges of \(G\) that remain when \(v\) is deleted. Let \(I_G(v) := \{ \, e \in E(G) : v \in e\, \} \) be the set of edges of \(G\) incident to \(v\). When \(V\) is finite, \(|I_G(v)|\) is the degree of \(v\). The next two lemmas show that deleting \(v\) removes exactly the edges of \(I_G(v)\), and count what remains. The count is used in lemma 4.5 to show that every vertex of a Laman graph on at least three vertices has degree at least two.
Let \(v \in V\). Then
that is, a pair \(e\) of vertices lies in \(E_{G}[\{ v\} ^c]\) if and only if \(e \in E(G)\) and \(v \notin e\).
An edge has both endpoints in \(\{ v\} ^c\) exactly when neither endpoint is \(v\), that is, when \(v \notin e\). So \(E_{G}[\{ v\} ^c]\) consists of the edges of \(G\) not incident to \(v\), which is \(E(G) \setminus I_G(v)\).
Let \(V\) be finite and let \(v \in V\). Then
By lemma 2.5, \(E(G)\) is the disjoint union of \(E_{G}[\{ v\} ^c]\) and \(I_G(v)\), so the cardinalities add.
2.3 Modularity: intersection, union, and supermodular counts
The map \(S \mapsto E_{G}[S]\) commutes with intersection but not with union. An edge with one endpoint in \(S \setminus T\) and the other in \(T \setminus S\) lies in \(E_{G}[S \cup T]\) but in neither \(E_{G}[S]\) nor \(E_{G}[T]\). Counting edges therefore gives an inequality (lemma 2.8). It becomes an identity, Jordán’s Lemma 2.1.1 [ Jor16 ] , when the number of these crossing edges is added to its left side. We need only the inequality, which is the counting step in the proof that tight sets are closed under union and intersection (theorem 3.14).
Let \(S, T \subseteq V\). Then \(E_{G}[S \cap T] = E_{G}[S] \cap E_{G}[T]\).
An edge has both endpoints in \(S \cap T\) if and only if both endpoints lie in \(S\) and both lie in \(T\).
Let \(V\) be finite and let \(S, T \subseteq V\). Then