# Abstract 3-Rigidity and Bivariate $C_{2}^{1}$-Splines I: Whiteley’s
Maximality Conjecture

Katie Clinch Department of Mathematical Informatics, Graduate School of
Information Science and Technology, University of Tokyo, Japan. Current
address: Department of Electrical and Electronic Engineering, University of
Melbourne, Parkville, Victoria, 3010, Australia. email:
<EMAIL_ADDRESS>Bill Jackson School of Mathematical Sciences,
Queen Mary University of London, Mile End Road, London E1 4NS, England. email:
<EMAIL_ADDRESS>and Shin-ichi Tanigawa Department of Mathematical
Informatics, Graduate School of Information Science and Technology, University
of Tokyo, 7-3-1 Hongo, Bunkyo-ku, 113-8656, Tokyo Japan. email:
<EMAIL_ADDRESS>
###### Abstract

A conjecture of Graver from 1991 states that the generic 3-dimensional
rigidity matroid is the unique maximal abstract 3-rigidity matroid with
respect to the weak order on matroids. Based on a close similarity between the
generic $d$-dimensional rigidity matroid and the generic
$C_{d-2}^{d-1}$-cofactor matroid from approximation theory, Whiteley made an
analogous conjecture in 1996 that the generic $C_{d-2}^{d-1}$-cofactor matroid
is the unique maximal abstract $d$-rigidity matroid for all $d\geq 2$. We
verify the case $d=3$ of Whiteley’s conjecture in this paper. A key step in
our proof is to verify a second conjecture of Whiteley that the ‘double
V-replacement operation’ preserves independence in the generic
$C_{2}^{1}$-cofactor matroid.

Keywords: graph rigidity, abstract rigidity matroid, bivariate spline,
cofactor matroid

††MSC 2010 classification : primary 52C25; secondary 05B35

##  1 Introduction

The statics of skeletal structures strongly depends on their underlying
graphs. This connection has been studied since the seminal work of James Clerk
Maxwell [20] in 1864, and combinatorial rigidity theory is now a fundamental
topic in structural rigidity [7, 22].

We will consider a $d$-dimensional (bar-joint) framework, which is a pair
$(G,{\bm{p}})$ consisting of a finite graph $G=(V,E)$ and a map
${\bm{p}}:V\rightarrow\mathbb{R}^{d}$. Asimow and Roth [1] and Gluck [5]
observed that the properties of rigidity and infinitesimal rigidity coincide
when ${\bm{p}}$ is generic (i.e., the set of coordinates in ${\bm{p}}$ is
algebraically independent over the rational field), and are completely
determined by $G$ and $d$. This fact enables us to define the generic
$d$-dimensional rigidity matroid ${\cal R}_{d}(G)$ on the edge set of $G$,
whose rank characterizes the rigidity of any generic framework $(G,{\bm{p}})$.
(See, e.g., [7, 18, 22] for more details.)

The generic $1$-dimensional rigidity matroid ${\cal R}_{1}(G)$ is equal to the
graphic matroid of $G$, and a celebrated theorem of Pollaczek-Geiringer [15]
and Laman [10] can be used to obtain a concise combinatorial formula for the
rank function of the generic $2$-dimensional rigidity matroid ${\cal
R}_{2}(G)$, see [11]. Finding a combinatorial description for ${\cal
R}_{3}(G)$ remains a fundamental open problem in the field which has inspired
a significant amount of research.

In 1991, Graver [6] suggested the approach of abstracting representative
properties of the $d$-dimensional rigidity matroid and recasting rigidity as a
matroid property. Suppose that $(G,{\bm{p}})$, $(G_{1},{\bm{p}}_{1})$ and
$(G_{2},{\bm{p}}_{2})$ are generic $d$-dimensional frameworks such that
$G=G_{1}\cup G_{2}$ and ${\bm{p}}_{i}$ is the restriction of ${\bm{p}}$ to
$V(G_{i})$ for $i=1,2$. It is intuitively clear that:

  * •

if $|V(G_{1})\cap V(G_{2})|\leq d-1$ then adding any edge between
$V(G_{1})\setminus V(G_{2})$ and $V(G_{2})\setminus V(G_{1})$ will restrict
the ‘flexibility’ of $(G,{\bm{p}})$, see Figure 1(a);

  * •

if $|V(G_{1})\cap V(G_{2})|\geq d$ and $(G_{1},{\bm{p}}_{1})$ and
$(G_{2},{\bm{p}}_{2})$ are both rigid then $(G,{\bm{p}})$ will be rigid, see
Figure 1(b).

Graver [6] observed that these physical properties can be described in terms
of matroid closure, and proposed to investigate all matroids which satisfy
these properties. More precisely, he defined a matroid $M$ on the edge set
$K(V)$ of the complete graph with vertex set $V$ to be an abstract
$d$-rigidity matroid if the following two properties hold:

(R1)

If $E_{1},E_{2}\subseteq K(V)$ with $|V(E_{1})\cap V(E_{2})|\leq d-1$, then
${\rm cl}_{M}(E_{1}\cup E_{2})\subseteq K(V(E_{1}))\cup K(V(E_{2}))$;

(R2)

If $E_{1},E_{2}\subseteq K(V)$ with ${\rm cl}_{M}(E_{1})=K(V(E_{1})),{\rm
cl}_{M}(E_{2})=K(V(E_{2}))$, and $|V(E_{1})\cap V(E_{2})|\geq d$, then ${\rm
cl}_{M}(E_{1}\cup E_{2})=K(V(E_{1}\cup E_{2}))$,

where ${\rm cl}_{M}$ denotes the closure operator of $M$. The generic
$d$-dimensional rigidity matroid for $K(V)$, ${\cal R}_{d}(V)$, is an example
of an abstract $d$-rigidity matroid. Graver [6] conjectured that, for all
$d\geq 1$, there is a unique maximal abstract $d$-rigidity matroid on $K(V)$
with respect to the weak order of matroids, and further that ${\cal R}_{d}(V)$
is this maximal matroid. He verified his conjecture for $d=1,2$ but N. J.
Thurston (see, [7, page 150]) subsequently showed that ${\cal R}_{d}(V)$ is
not the unique maximal abstract $d$-rigidity matroid when $d\geq 4$. We will
verify the first part of Graver’s conjecture when $d=3$.111The first part of
Graver’s conjecture, that there exists a unique maximal abstract $d$-rigidity
matroid on $K(V)$, would follow for all $d$ as a special case of the main
result in a preprint of Sitharam and Vince [16]. Unfortunately this more
general result is false, see [14, 9]. The second part remains as a long-
standing open problem.

######  Conjecture 1.1 (Maximality conjecture).

The generic $3$-dimensional rigidity matroid on $K(V)$ is the unique maximal
abstract $3$-rigidity matroid on $K(V)$.

(a)

(b)

Figure 1: Examples in $d=3$: (a) When $|V(G_{1})\cap V(G_{2})|=2$,
$(G_{1},{\bm{p}}_{1})$ and $(G_{2},{\bm{p}}_{2})$ can rotate about the line
through the points of $V(G_{1})\cap V(G_{2})$, and adding any edge between
$V(G_{1})\setminus V(G_{2})$ and $V(G_{2})\setminus V(G_{1})$ will restrict
this motion. (b) Rigid frameworks $(G_{1},{\bm{p}}_{1})$ and
$(G_{2},{\bm{p}}_{2})$ are glued together along three vertices, and the
resulting framework is rigid.

Whiteley [22] found another candidate for a maximal abstract $d$-rigidity
matroid from approximation theory. Consider a plane polygonal domain $D$ which
has been subdivided into a set of polygonal faces $\Delta$. A bivariate
$C_{s}^{r}$-spline over $\Delta$ is a function on $D$ which is continuously
differentiable $r$ times and is given by a polynomial of degree $s$ over each
face of $\Delta$. The set of all $C_{s}^{r}$-splines over $\Delta$ forms a
vector space $S_{s}^{r}(\Delta)$, and determining the dimension of
$S_{s}^{r}(\Delta)$ is a major question in this area. When $r=0$ and $d=1$,
$S_{1}^{0}(\Delta)$ is the space of piecewise linear functions, and Maxwell’s
reciprocal diagram  gives a concrete correspondence between
$S_{1}^{0}(\Delta)$ and the self-stresses of the $1$-skeleton of $\Delta$,
regarded as a 2-dimensional framework $(G,{\bm{p}})$. Whiteley [19, 21, 22]
extended this connection further and demonstrated how the dimension of
$S_{s}^{r}(\Delta)$ can be computed from the rank of the $C_{s}^{r}$-cofactor
matrix $C_{s}^{r}(G,{\bm{p}})$, which is a variant of the incidence matrix of
$G$ in which the entries are replaced by block matrices whose entries are
polynomials in ${\bm{p}}$. Billera [2] used Whiteley’s approach to solve a
conjecture of Strang on the generic dimension of $S_{s}^{1}(\Delta)$.

The definition of $C_{s}^{r}(G,{\bm{p}})$ is not dependent on the fact that
$(G,{\bm{p}})$ is a realisation of $G$ in the plane without crossing edges and
is equally valid for any 2-dimensional framework $(G,{\bm{p}})$. Moreover, in
the case when $r=s-1$, each row of $C_{s}^{s-1}(G,{\bm{p}})$ is associated
with a distinct edge of $G$, and hence the row matroid of
$C_{s}^{s-1}(G,{\bm{p}})$ is a matroid defined on $E(G)$. We refer to this
matroid as the $C_{s}^{s-1}$-cofactor matroid for $(G,{\bm{p}})$ and denote it
by ${\cal C}_{s}^{s-1}(G,{\bm{p}})$. Since the matroids ${\cal
C}_{s}^{s-1}(G,{\bm{p}})$ are the same for all generic ${\bm{p}}$, the generic
$C_{s}^{s-1}$-cofactor matroid of $G$, denoted by ${\cal C}_{s}^{s-1}(G)$, is
defined to be ${\cal C}_{s}^{s-1}(G,{\bm{p}})$ for any generic ${\bm{p}}$.
(See Section 2.1 for a formal definition). Let ${\cal C}_{d-1}^{d-2}(V)={\cal
C}_{d-1}^{d-2}(K(V))$. Whiteley [22] showed that ${\cal C}_{d-1}^{d-2}(V)$ is
an example of an abstract $d$-rigidity matroid and pointed out that ${\cal
C}_{d-1}^{d-2}(V)={\cal R}_{d}(V)$ when $d=2$. He also showed that ${\cal
C}_{d-1}^{d-2}(V)$ is a counterexample to Graver’s original maximality
conjecture for all $d\geq 4$ and conjectured further that ${\cal
C}_{d-1}^{d-2}(V)$ is the maximal abstract $d$-rigidity matroid for all $d\geq
2$.

In this paper we verify Whiteley’s conjecture for $d=3$, and hence prove the
cofactor counterpart of Conjecture 1.1:

######  Theorem 1.2.

The generic $C_{2}^{1}$-cofactor matroid ${\cal C}_{2}^{1}(V)$ is the unique
maximal abstract 3-rigidity matroid on $K(V)$.

The most difficult part of the proof of Theorem 1.2 is to show that a certain
graph operation (called the double V-replacement operation) preserves
independence in the generic $C_{2}^{1}$-cofactor matroid. This is related to
another long-standing conjecture on the generic 3-dimensional rigidity
matroid, known as the Henneberg construction conjecture, which asks if every
base of the generic 3-dimensional rigidity matroid ${\cal R}_{3}(V)$ can be
constructed from $K_{4}$ by a sequence of simple graph operations (see [17, 4]
for more details). Based on a strong similarity between rigidity matroids and
cofactor matroids, Whiteley [19, page 55] posed a corresponding Henneberg
construction conjecture for the generic $C_{2}^{1}$-cofactor matroid. We will
verify this conjecture.

In his survey on generic rigidity and cofactor matroids, Whiteley gave a table
of properties and conjectures for the generic $3$-dimensional rigidity and
$C_{2}^{1}$-cofactor matroids [22, page 65]. The table below updates
Whiteley’s table with results from [8] and the current paper.

| Generic $3$-dim rigidity | Generic $C_{2}^{1}$-cofactor
---|---|---
rank $K_{n}$, $n\geq 3$ | $3n-6$ | $3n-6$
0-extension (vertex addition) | YES | YES
1-extension (edge split) | YES | YES
abstract 3-rigidity | YES | YES
vertex splitting | YES | YES
simplicial 2-surfaces | Rigid [5] | Rigid [2]
coning | YES | YES
X-replacement | Conjectured | YES [22]
double V-replacement | Conjectured | YES (Theorem 3.3)
Dress conjecture | NO [8] | NO [8]
$K_{4,6}$ | Base | Base
$K_{5,5}$ | Circuit | Circuit
maximal abstract 3-rigidity matroid | Conjectured | YES (Theorem 1.2)

We will give a combinatorial characterization of the rank function of the
maximal abstract 3-rigidity matroid ${\cal C}_{2}^{1}(V)$ in a companion paper
[3] to this one, and hence solve the cofactor counterpart to the combinatorial
characterization problem for $3$-dimensional rigidity. Theorem 1.2 is a key
ingredient of the proof in this companion paper.

This paper focuses on proving Theorem 1.2, and hence we restrict our attention
to $C_{2}^{1}$-cofactor matroids. In Section 2, we first provide a brief
introduction to $C_{2}^{1}$-cofactor matroids, and then give a detailed
roadmap for the proof of Theorem 1.2.

##  2 Preliminaries

In this section we give a formal definition of $C_{2}^{1}$-cofactor matroids
and describe their fundamental properties. We then give a roadmap for the
proof of Theorem 1.2.

We use the following notation throughout this paper. For a finite set
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, let $K(V)$, or
$K(v_{1},v_{2},\ldots,v_{n})$, denote the edge set of the complete graph with
vertex set $V$. For a graph $G=(V,E)$ and $v\in V$, let $N_{G}(v)$ be the set
of neighbors of $v$ in $G$ and $\hat{N}_{G}(v)=N_{G}(v)\cup\\{v\\}$ be the
closed neighborhood of $v$ in $G$. For an edge set $F$ and a vertex $v$, let
$d_{F}(v)$ denote the number of edges of $F$ incident to $v$. A star on $n$
vertices is a tree with $n$ vertices in which one vertex is adjacent to all
other vertices.

We often regard a map ${\bm{p}}:V\to{\mathbb{R}}^{k}$ as a $k|V|$-dimensional
vector. The inner product ${\bm{p}}\cdot{\bm{q}}$ of two maps
${\bm{p}},{\bm{q}}:V\to{\mathbb{R}}^{k}$ is given by this identification.

For vectors ${\bm{v}}_{1},\dots,{\bm{v}}_{k}$ in a Euclidean space, let
$\langle{\bm{v}}_{1},\dots,{\bm{v}}_{k}\rangle$ be their linear span.

For a set $Z$ of real numbers, let $\mathbb{Q}(Z)$ denote the smallest
subfield of $\mathbb{R}$ that contains the rationals and $Z$.

The closure operator and the rank function of a matroid ${\cal M}$ are denoted
by ${\rm cl}_{{\cal M}}$ and $r_{{\cal M}}$, respectively. The weak order for
matroids is a partial order over all matroids with the same groundset $E$,
where for two matroids ${\cal M}_{i}=(E,r_{{\cal M}_{i}})\ (i=1,2)$ we have
${\cal M}_{1}\preceq{\cal M}_{2}$ if $r_{{\cal M}_{1}}(X)\leq r_{{\cal
M}_{2}}(X)$ holds for all $X\subseteq E$.

###  2.1 The $C_{2}^{1}$-cofactor Matrix

Given two points $p_{i}=(x_{i},y_{i})$ and $p_{j}=(x_{j},y_{j})$ in
${\mathbb{R}}^{2}$, we define $D(p_{i},p_{j})\in\mathbb{R}^{3}$ by

$D(p_{i},p_{j})=((x_{i}-x_{j})^{2},(x_{i}-x_{j})(y_{i}-y_{j}),(y_{i}-y_{j})^{2}).$

For a 2-dimensional framework $(G,{\bm{p}})$ with vertex set
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, we simply write $D(v_{i},v_{j})$ for
$D({\bm{p}}(v_{i}),{\bm{p}}(v_{j}))$ when ${\bm{p}}$ is clear from the
context.

We define the $C^{1}_{2}$-cofactor matrix of a 2-dimensional framework
$(G,{\bm{p}})$ to be the matrix $C_{2}^{1}(G,{\bm{p}})$ of size $|E|\times
3|V|$ in which each vertex is associated with a set of three consecutive
columns, each edge is associated with a row, and the row associated with the
edge $e=v_{i}v_{j}$ with $i<j$ is

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{i}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle v_{j}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\e=v_{i}v_{j}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle D(v_{i},v_{j})$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-D(v_{i},v_{j})$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\cdots 0$\hfil\kern 5.0pt\crcr}}}}\right]$}}.$

For example, for $(K_{4},{\bm{p}})$ with ${\bm{p}}(v_{1})=(0,0)$,
${\bm{p}}(v_{2})=(1,0)$, ${\bm{p}}(v_{3})=(0,1)$ and
${\bm{p}}(v_{4})=(-1,-1)$,

$C_{2}^{1}(K_{4},{\bm{p}})=\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{1}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{2}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{3}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{4}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\\\v_{1}v_{2}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{1}v_{3}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{1}v_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1\\\v_{2}v_{3}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{2}v_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
4$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-4$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1\\\v_{3}v_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 4$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-4$\hfil\kern 5.0pt\crcr}}}}\right]$}}.$

(Our definition is slightly different to that given by Whiteley [22], but the
two definitions are equivalent up to elementary column operations.) It is
known that the space $S_{2}^{1}(\Delta)$ of bivariate $C_{2}^{1}$-splines over
a subdivision $\Delta$ of a polygonal domain in the plane is linearly
isomorphic to the left kernel of $C_{2}^{1}(G,{\bm{p}})$ if $(G,{\bm{p}})$ is
the 1-skeleton of $\Delta$. See, [22] for more details.

###  2.2 $C_{2}^{1}$-motions

As mentioned above, the left kernel of the $C_{2}^{1}$-cofactor matrix
$C_{2}^{1}(G,{\bm{p}})$ has an important role in the analysis of
$C_{2}^{1}$-splines. An analogous situation occurs in rigidity theory where
the left kernel of the rigidity matrix is the space of self-stresses of the
framework. The right kernel of the rigidity matrix plays an equally important
role in rigidity theory since it is the space of infinitesimal motions of the
framework. In order to apply techniques from rigidity theory to cofactor
matrices, we will also consider the right kernel of the $C_{2}^{1}$-cofactor
matrix.

Let $G=(V,E)$ be a graph and ${\bm{p}}:V\to{\mathbb{R}}^{2}$ such that
${\bm{p}}(v_{i})=(x_{i},y_{i})\in\mathbb{R}^{2}$ for all $v_{i}\in V$. A
$C_{2}^{1}$-motion (or simply, a motion) of $(G,{\bm{p}})$ is a map
${\bm{q}}:V\rightarrow\mathbb{R}^{3}$ satisfying

$D(v_{i},v_{j})\cdot({\bm{q}}(v_{i})-{\bm{q}}(v_{j}))=0\qquad(v_{i}v_{j}\in
E).$ (1)

The $C_{2}^{1}$-cofactor matrix $C_{2}^{1}(G,{\bm{p}})$ defined in Section 2.1
is the matrix of coefficients of this system of linear equations in the
variable ${\bm{q}}$, and hence each $C_{2}^{1}$-motion ${\bm{q}}$ is a vector
in the right kernel $Z(G,{\bm{p}})$ of $C_{2}^{1}(G,{\bm{p}})$.

Whiteley [22] showed that $Z(G,{\bm{p}})$ has dimension at least six when
${\bm{p}}(V)$ affinely spans ${\mathbb{R}}^{2}$ by showing that the
$C_{2}^{1}$-motions ${\bm{q}}_{i}^{*}:V\rightarrow\mathbb{R}^{3}$, $1\leq
i\leq 6$, defined by

$\displaystyle{\bm{q}}_{1}^{*}(v_{i})$ $\displaystyle=(1,0,0),$
$\displaystyle{\bm{q}}_{2}^{*}(v_{i})$ $\displaystyle=(0,1,0),$
$\displaystyle{\bm{q}}_{3}^{*}(v_{i})$ $\displaystyle=(0,0,1),$ (2)
$\displaystyle{\bm{q}}_{4}^{*}(v_{i})$ $\displaystyle=(y_{i},-x_{i},0),$
$\displaystyle{\bm{q}}_{5}^{*}(v_{i})$ $\displaystyle=(0,-y_{i},x_{i})$
$\displaystyle{\bm{q}}_{6}^{*}(v_{i})$
$\displaystyle=(y_{i}^{2},-2x_{i}y_{i},x_{i}^{2})$ (3)

for each $v_{i}\in V$, are linearly independent vectors in $Z(G,{\bm{p}})$ for
all $G$. (We have adjusted the values of the ${\bm{q}}_{i}^{*}$ given in [22]
to fit our modified definition of $C_{2}^{1}(G,{\bm{p}})$.) We will refer to a
$C_{2}^{1}$-motion that can be described as a linear combination of the
${\bm{q}}_{i}^{*},1\leq i\leq 6$ as a trivial $C_{2}^{1}$-motion, and let
$Z_{0}(G,{\bm{p}})$ be the space of all trivial $C_{2}^{1}$-motions.

The following terminologies are $C_{2}^{1}$-cofactor analogues of standard
terminologies in rigidity theory. We say that a framework $(G,{\bm{p}})$ is:
$C_{2}^{1}$-rigid if $Z(G,{\bm{p}})=Z_{0}(G,{\bm{p}})$;
$C_{2}^{1}$-independent if the rows of $C_{2}^{1}(G,{\bm{p}})$ are linearly
independent; minimally $C_{2}^{1}$-rigid if $(G,{\bm{p}})$ is both
$C_{2}^{1}$-rigid and $C_{2}^{1}$-independent; a $k$-degree of freedom
framework, or $k$-dof framework for short, if $\dim Z(G,{\bm{p}})=6+k$. We
will use the same terms for the graph $G$ if $(G,{\bm{p}})$ has the
corresponding properties for some (or equivalently, every) generic ${\bm{p}}$.

###  2.3 Generic ${C}_{2}^{1}$-cofactor Matroids

The generic $C_{2}^{1}$-cofactor matroid, ${\cal C}_{2,n}^{1}$, is the matroid
on $E(K_{n})$ in which independence is given by the linear independence of the
rows of $C_{2}^{1}(K_{n},{\bm{p}})$ for any generic ${\bm{p}}$. We will
sometimes simplify ${\cal C}_{2,n}^{1}$ to ${\cal C}_{n}$ or even ${\cal C}$
when it is clear from the context. Note that a graph $G$ with $n$ vertices is
minimally $C_{2}^{1}$-rigid (resp., $C_{2}^{1}$-independent) if and only if
$E(G)$ is a base (resp., an independent set) of ${\cal C}_{2,n}^{1}$.

Since $\dim Z(K_{n},{\bm{p}})\geq\dim Z_{0}(K_{n},{\bm{p}})=6$ holds when
$n\geq 3$ and ${\bm{p}}$ is generic, the rank of ${\cal C}_{2,n}^{1}$ is at
most $3n-6$ for all $n\geq 3$. Whiteley [22, Corollary 11.3.15] showed that
the rank of ${\cal C}_{2,n}^{1}$ is equal to $3n-6$ when $n\geq 3$, and, more
significantly, that ${\cal C}_{2,n}^{1}$ is an abstract $3$-rigidity matroid.
Our main result, Theorem 1.2, verifies that ${\cal C}_{2,n}^{1}$ is the unique
maximal abstract $3$-rigidity matroid on $E(K_{n})$.

###  2.4 Pinning

The technique of pinning, i.e. specifying the value of a motion at one or more
vertices, is frequently used when dealing with a $k$-dof framework
$(G,{\bm{p}})$ in rigidity theory, and we will also use this technique in our
analysis. The following technical lemmas will be used only in Sections 5 and
6, so the reader may wish to skip this subsection and refer back to it later.

For $v_{s}\in V(G)$ and $t\in\\{1,2,3\\}$, let ${\bf
e}_{s,t}:V\rightarrow{\mathbb{R}}^{3}$ be such that ${\bf e}_{s,t}(v_{s})$ is
the unit vector with $1$ at the $t$-coordinate and zeros elsewhere, and ${\bf
e}_{s,t}(v_{i})=0$ for $i\neq s$.

######  Lemma 2.1.

Let $(G,{\bm{p}})$ be a $k$-dof framework such that
${\bm{p}}(v_{i})=(x_{i},y_{i})\in\mathbb{R}^{2}$ for all $v_{i}\in V(G)$;
$v_{a},v_{b},v_{c}$ be three distinct vertices such that
$(y_{a}-y_{b})(y_{a}-y_{c})(y_{b}-y_{c})\neq 0$;
${\bm{q}}_{0},{\bm{q}}_{1},\dots,{\bm{q}}_{k}$ be motions of $(G,{\bm{p}})$
such that ${\bm{q}}_{1},\dots,{\bm{q}}_{k}$ are linearly independent and

${\bm{q}}_{i}\cdot{\bf e}_{s,t}=0\text{ for all
}(s,t)\in\\{(a,1),(a,2),(a,3),(b,1),(b,2),(c,1)\\}$ (4)

for every $i\in\\{0,1,\ldots,k\\}$. Then
$Z(G,{\bm{p}})=Z_{0}(G,{\bm{p}})\oplus\langle{\bm{q}}_{1},\dots,{\bm{q}}_{k}\rangle$
and ${\bm{q}}_{0}\in\langle{\bm{q}}_{1},\dots,{\bm{q}}_{k}\rangle$.

###### Proof.

Suppose
$\sum_{i=1}^{k}\mu_{i}{\bm{q}}_{i}=\sum_{j=1}^{6}\lambda_{j}{\bm{q}}^{*}_{j}$
for some $\mu_{i},\lambda_{j}\in\mathbb{R}$. Then (4) gives

$\sum_{j=1}^{6}\lambda_{j}({\bm{q}}^{*}_{j}\cdot{\bf e}_{s,t})=0\text{ for
every }(s,t)\in\\{(a,1),(a,2),(a,3),(b,1),(b,2),(c,1)\\}.$

By the definition of $q_{i}^{*}$ in (2) and (3), this system of equations can
be written as

$\begin{pmatrix}1&0&0&y_{a}&0&y_{a}^{2}\\\ 0&1&0&-x_{a}&-y_{a}&-2x_{a}y_{a}\\\
0&0&1&0&x_{a}&x_{a}^{2}\\\ 1&0&0&y_{b}&0&y_{b}^{2}\\\
0&1&0&-x_{b}&-y_{b}&-2x_{b}y_{b}\\\
1&0&0&y_{c}&0&y_{c}^{2}\end{pmatrix}\begin{pmatrix}\lambda_{1}\\\
\lambda_{2}\\\ \lambda_{3}\\\ \lambda_{4}\\\ \lambda_{5}\\\
\lambda_{6}\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\\\ 0\\\ 0\\\
0\end{pmatrix}.$

Let $Q$ denote the matrix of coefficients of this system. Then $\det
Q=(y_{a}-y_{b})^{2}(y_{c}-y_{a})(y_{b}-y_{c})\neq 0$. Hence $Q$ is non-
singular, and $\lambda_{j}=0$ for all $1\leq j\leq 6$. Thus
$Z_{0}(G,{\bm{p}})\cap\langle{\bm{q}}_{1},\dots,{\bm{q}}_{k}\rangle=\\{0\\}$.
The fact that $(G,{\bm{p}})$ is a $k$-dof framework now gives
$Z(G,{\bm{p}})=Z_{0}(G,{\bm{p}})\oplus\langle{\bm{q}}_{1},\dots,{\bm{q}}_{k}\rangle$.

Since ${\bm{q}}_{0}$ is a motion, we have
${\bm{q}}_{0}=\sum_{i=1}^{k}\mu_{i}^{\prime}{\bm{q}}_{i}+\sum_{j=1}^{6}\lambda_{j}^{\prime}{\bm{q}}^{*}_{j}$
for some $\mu_{i}^{\prime},\lambda_{j}^{\prime}\in\mathbb{R}$. We can use (4)
to obtain

$\sum_{j=1}^{6}\lambda_{j}^{\prime}({\bm{q}}^{*}_{j}\cdot{\bf
e}_{s,t})=0\text{ for every
}(s,t)\in\\{(a,1),(a,2),(a,3),(b,1),(b,2),(c,1)\\}.$

The same argument as in the previous paragraph now gives
$\lambda_{j}^{\prime}=0$ for all $1\leq j\leq 6$. In other words,
${\bm{q}}_{0}$ is a linear combination of ${\bm{q}}_{1},\dots,{\bm{q}}_{k}$. ∎

Suppose $v_{a},v_{b},v_{c}$ are distinct vertices in a framework
$(G,{\bm{p}})$. We define the extended $C_{2}^{1}$-cofactor matrix
$\tilde{C}(G,{\bm{p}})$ (with respect to $(v_{a},v_{b},v_{c})$) to be the
matrix of size $3|V|\times(|E|+6)$ obtained from $C(G,{\bm{p}})$ by adding the
six rows, ${\bf e}_{a,1},{\bf e}_{a,2},{\bf e}_{a,3},{\bf e}_{b,1},{\bf
e}_{b,2},{\bf e}_{c,1}$.

For example, for $(K_{4},{\bm{p}})$ with ${\bm{p}}(v_{1})=(0,0)$,
${\bm{p}}(v_{2})=(1,0)$, ${\bm{p}}(v_{3})=(0,1)$ and
${\bm{p}}(v_{4})=(-1,-1)$, the extended $C_{2}^{1}$-cofactor matrix with
respect to $(v_{1},v_{2},v_{3})$ is

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{1}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{2}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{3}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
v_{4}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle\\\$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{1}v_{2}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{1}v_{3}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{1}v_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1\\\v_{2}v_{3}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\\\v_{2}v_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
4$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-4$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1\\\v_{3}v_{4}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
0$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
1$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle 2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 4$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-1$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-2$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-4$\hfil\kern 5.0pt\crcr}}}}\right]$}}.$

######  Lemma 2.2.

Let $(G,{\bm{p}})$ be a framework with $|E(G)|=3|V(G)|-(6+k)$, and denote
${\bm{p}}(v_{i})=(x_{i},y_{i})$ for each $v_{i}\in V$. Let
$\tilde{C}(G,{\bm{p}})$ be the extended $C_{2}^{1}$-cofactor matrix with
respect to three vertices $(v_{a},v_{b},v_{c})$ and suppose that
$(y_{a}-y_{b})(y_{a}-y_{c})(y_{b}-y_{c})\neq 0$. Then $\tilde{C}(G,{\bm{p}})$
is row independent if and only if $\dim Z(G,{\bm{p}})=6+k$.

###### Proof.

If $\tilde{C}(G,{\bm{p}})$ is row independent, then $C(G,{\bm{p}})$ is row
independent and hence

$\dim Z(G,{\bm{p}})=3|V(G)|-|E(G)|=6+k.$

To see the converse, suppose $\dim Z(G,{\bm{p}})=6+k$ but
$\tilde{C}(G,{\bm{p}})$ is row dependent. We can choose $k+1$ linearly
independent $C_{2}^{1}$-motions ${\bm{q}}_{0},{\bm{q}}_{1},\dots,{\bm{q}}_{k}$
of $(G,{\bm{p}})$ from the kernel of $\tilde{C}(G,{\bm{p}})$. Then each
${\bm{q}}_{i}$ satisfies (4). Hence, by Lemma 2.1,
${\bm{q}}_{0}\in\langle{\bm{q}}_{1},\dots,{\bm{q}}_{k}\rangle$, which is a
contradiction. ∎

###  2.5 Roadmap for the proof of Theorem 1.2

The proof of Theorem 1.2 is structured as follows:

$\text{Theorem~{}\ref{thm:cofactor} $\overset{\mathrm{Sec~{}\ref{subsec:K_d
matroid}}}{\Longleftarrow}$ Theorem~{}\ref{thm:K_d+2matroid}
$\overset{\mathrm{Sec~{}\ref{subsec:proof_of_thm12}}}{\Longleftarrow}$
Theorem~{}\ref{thm:doubleVconj}
$\overset{\mathrm{Sec~{}\ref{sec:doubleV}}}{\Longleftarrow}$
Theorem~{}\ref{thm:doubleV}
$\overset{\mathrm{Sec~{}\ref{sec:bad}}}{\Longleftarrow}$
Theorem~{}\ref{thm:well-behaved0}$\overset{\mathrm{Sec~{}\ref{sec:well-
behaved}}}{\Longleftarrow}$ Theorem~{}\ref{thm:well-behaved}}.$

Below we briefly explain each theorem and step.

##### Section 3.2:

It is known that the edge set of $K_{5}$ is a circuit in any abstract
3-rigidity matroid (see, e.g., [7] or Theorem 3.4). A matroid satisfying this
circuit property is called a $K_{5}$-matroid. The class of $K_{5}$-matroids is
slightly larger than the set of abstract 3-rigidity matroids. Theorem 3.6
states that the generic $C_{2}^{1}$-cofactor matroid ${\cal C}_{2}^{1}(K_{n})$
is the unique maximal matroid in the poset of all $K_{5}$-matroids on
$E(K_{n})$. Thus Theorem 3.6 is a stronger version of Theorem 1.2.

##### Section 3.3:

Graver [6] proved that the generic 2-dimensional rigidity matroid is the
unique maximal abstract 2-rigidity matroid based on that fact that any base of
the generic 2-dimensional rigidity matroid can be constructed from $K_{3}$ by
a sequence of two simple graph operations, called the Henneberg constructions.
Following the same approach as that of Graver [6], we show that Theorem 3.6
will follow from an inductive construction of the bases of the ${\cal
C}_{2}^{1}$-cofactor matroid. For this purpose, Whiteley [22] already verified
that various graph operations preserve $C_{2}^{1}$-independence. However,
there remained one operation, double V-replacement, that Whiteley could not
show preserved independence. (See Figure 3 for an example of double
V-replacement.). We confirm that it does preserve independence in Theorem 3.3.
The remainder of the paper is devoted to proving this result.

##### Section 4:

By combining existing results from [22] and a simple combinatorial argument in
Section 4, we prove that Theorem 3.3 holds in all but one special case. This
remaining special case is when ${\rm cl}(E(G-v_{0}))\cap K(N_{G}(v_{0}))$
forms a star on five vertices as shown in Figure 4, where $v_{0}$ denotes the
vertex created by the double $V$-replacement. We formulate a new result,
Theorem 4.6, to deal with this remaining special case.

##### Section 5:

In Section 5, we first show that, if the statement of Theorem 4.6 fails, then
the framework created by the double V-replacement operation has a very special
$C_{2}^{1}$-motion. Theorem 5.8 states that such a motion cannot exist in any
generic $1$-dof framework.

##### Section 6:

We prove Theorem 5.8. Our inductive proof requires a more general inductive
statement, Theorem 6.1, which concerns frameworks with at most two degrees of
freedom. The proof is rather long so we first outline the main ideas in
Section 6.2.

##  3 Inductive Construction and Proof of Theorem 1.2

###  3.1 Inductive Construction

Our proof of Theorem 1.2 uses the following 3-dimensional versions of standard
graph operations from rigidity theory. Given a graph $H$:

  * •

the _$0$ -extension_ operation adds a new vertex $v$ and three new edges from
$v$ to vertices in $H$;

  * •

the $1$-extension operation chooses an edge $e$ of $H$ and adds a new vertex
$v$ and four new edges from $v$ to vertices in $H-e$ with the proviso that two
of the new edges join $v$ to the end-vertices of $e$;

  * •

the X-replacement operation chooses two non-adjacent edges $e$ and $f$ of $H$
and adds a new vertex $v$ and five new edges from $v$ to vertices in
$H-\\{e,f\\}$ with the proviso that four of the new edges join $v$ to the end-
vertices of $e$ and $f$;

  * •

the V-replacement operation chooses two adjacent edges $e$ and $f$ of $H$ and
adds a new vertex $v$ and five new edges from $v$ to vertices in $H-\\{e,f\\}$
with the proviso that three of the new edges join $v$ to the end-vertices of
$e$ and $f$;

  * •

the vertex splitting operation chooses a vertex $u$ of $H$ and pairwise
disjoint sets $U_{1},U_{2},U_{3}$ with $U_{1}\cup U_{2}\cup U_{3}=N_{H}(u)$
and $|U_{2}|=2$, deletes all edges from $u$ to $U_{3}$, and then adds a new
vertex $v$ and $|U_{3}|+3$ new edges from $v$ to each vertex in $U_{2}\cup
U_{3}\cup\\{u\\}$.

Whiteley [22, Lemmas 10.1.5 and 10.2.1, Theorems 10.2.7 and 10.3.1] showed
that all but one of these operations preserve $C_{2}^{1}$-independence:

######  Lemma 3.1.

The $0$-extension, $1$-extension, X-replacement, and vertex splitting
operations preserve $C_{2}^{1}$-independence.

In general V-replacement may not preserve $C_{2}^{1}$-independence, but there
is an important special case when it does.

######  Lemma 3.2.

Suppose that $v_{1},v_{2},v_{3},v_{4},v_{5}$ are vertices of a
$C_{2}^{1}$-independent graph $H=(V,E)$, $e=v_{1}v_{2},f=v_{1}v_{3}$ are edges
of $H$ and $v_{1}v_{4},v_{1}v_{5}$ belong to the closure of $E-e-f$ in the
$C^{1}_{2}$-cofactor matroid on $K(V)$. Then the graph $G$ obtained from
$H-e-f$ by adding a new vertex $v$ and new edges
$vv_{1},vv_{2},vv_{3},vv_{4},vv_{5}$ is $C_{2}^{1}$-independent.

###### Proof.

Let $\operatorname{cl}(.)$ denote the closure operator in the
$C^{1}_{2}$-cofactor matroid on $K(V)$. Since
$v_{1}v_{4},v_{1}v_{5}\in\operatorname{cl}(E-e-f)$, we may choose a base $B$
of $\operatorname{cl}(E-e-f)$ with $v_{1}v_{4},v_{1}v_{5}\in B$. Then the
graph $H^{\prime}=(B,B+e+f)$ is $C_{2}^{1}$-independent and we can now apply
the vertex splitting operation at $v_{1}$ to deduce that the graph
$G^{\prime}$ obtained from $H^{\prime}-e-f$ by adding a new vertex $v$ and new
edges $vv_{1},vv_{2},vv_{3},vv_{4},vv_{5}$ is $C_{2}^{1}$-independent, see
Figure 2. This and the fact that
$\operatorname{cl}(B)=\operatorname{cl}(E-e-f)$ imply that $G$ is
$C_{2}^{1}$-independent. ∎

Lemma 3.2 will be used several times in our proofs

Whiteley [22] conjectured that another special case of V-replacement preserves
$C_{2}^{1}$-independence: if $H\cup\\{e_{1},e_{2}\\}$ and
$H\cup\\{e_{1}^{\prime},e_{2}^{\prime}\\}$ are both $C_{2}^{1}$-independent
for two pairs of adjacent edges $e_{1},e_{2}$ and
$e_{1}^{\prime},e_{2}^{\prime}$ with the property that the common endvertex of
$e_{1},e_{2}$ is distinct from that of $e_{1}^{\prime},e_{2}^{\prime}$, then
the graph $G$ obtained by adding a new vertex $v_{0}$ of degree five to $H$ in
such a way that the endvertices of $e_{1},e_{2},e_{1}^{\prime},e_{2}^{\prime}$
are all neighbours of $v_{0}$, is $C_{2}^{1}$-independent. See Figure 3. This
operation is referred to as double V-replacement since $G$ can be constructed
from both $G-v_{0}+e_{1}+e_{2}$ and $G-v_{0}+e_{1}^{\prime}+e_{2}^{\prime}$ by
a V-replacement. We will verify Whiteley’s conjecture:

Figure 2: An extension operation which can be considered as a special case of
both V-replacement and vertex splitting.  Figure 3: An example of double
V-replacement.

######  Theorem 3.3.

The double V-replacement operation preserves $C_{2}^{1}$-independence.

Lemma 3.1 and Theorem 3.3 imply that we can construct all minimally
$C_{2}^{1}$-rigid graphs from copies of $K_{4}$ with a ‘Henneberg tree
construction’ using the 0-, 1-, X- and double V-extension operations. We refer
the reader to [17, 22] for more details.

The proof of Theorem 3.3 will be spread over Sections 4, 5 and 6 of this
paper. To motivate this rather long and technical proof we show in the
remainder of this section how (a generalisation of) our main result, Theorem
1.2, can be deduced easily from Lemma 3.1 and Theorem 3.3.

###  3.2 $K_{t}$-matroids

Let $n$ and $t$ be positive integers with $t\leq n$. A matroid ${\cal M}$ on
the edge set of a complete graph $K_{n}$ is said to be a $K_{t}$-matroid if
the edge set of every copy of $K_{t}$ in $K_{n}$ is a circuit in ${\cal M}$.
The following simple characterization of abstract $d$-rigidity matroids due to
Nguyen[13, Theorem 2.2] implies that every abstract $d$-rigidity matroid is a
$K_{d+2}$-matroid.

######  Theorem 3.4.

Let $n,d$ be positive integers with $n\geq d+2$ and ${\cal M}$ be a matroid on
$E(K_{n})$. Then ${\cal M}$ is an abstract $d$-rigidity matroid if and only if
${\cal M}$ is a $K_{d+2}$-matroid with rank $dn-{d+1\choose 2}$.

We will prove a stronger version of Theorem 1.2 by showing that the
$C^{1}_{2}$-cofactor matroid is the unique maximal matroid in the family of
$K_{5}$-matroids. (This strengthening will be needed in our companion paper
[3].)

Our next lemma shows that $dn-{d+1\choose 2}$ is an upper bound on the rank of
any $K_{d+2}$-matroid on $E(K_{n})$ when $n$ is sufficiently large.

######  Lemma 3.5.

Suppose that ${\cal M}$ is a $K_{d+2}$-matroid on $E(K_{n})$ for $n\geq d+2$.
Then ${\cal M}$ has rank at most $dn-{{d+1}\choose{2}}$.

###### Proof.

We proceed by induction on $n$. The claim is trivial when $n=d+2$.

Suppose $n>d+2$, and denote the vertex set of $K_{n}$ by
$\\{v_{1},\dots,v_{n}\\}$. Let $K$ be the edge set of the complete graph on
$\\{v_{1},\dots,v_{n-1}\\}$. Since ${\cal M}|_{K}$ is a $K_{d+2}$-matroid, the
rank of $K$ in ${\cal M}$ is at most $d(n-1)-{d+1\choose 2}$ by induction. Let
$K^{\prime}=K+\\{v_{1}v_{n},v_{2}v_{n},\dots,v_{d}v_{n}\\}$. We show
$K^{\prime}$ spans $E(K_{n})$.

For each $i=d+1,\dots,n-1$, let $C_{i}$ be the edge set of the complete graph
on $\\{v_{1},v_{2},\dots,v_{d-1},v_{d},v_{n},v_{i}\\}$. Note that $K^{\prime}$
contains all edges of $C_{i}$ except $v_{i}v_{n}$. Since ${\cal M}$ is a
$K_{d+2}$-matroid, $v_{i}v_{n}$ is spanned by $K^{\prime}$. Hence $K^{\prime}$
spans $E(K_{n})$, and the rank of ${\cal M}$ is at most
$|K^{\prime}|=|K|+d=dn-{d+1\choose 2}$. ∎

Theorem 3.4 and Lemma 3.5 imply that an abstract $d$-rigidity matroid is a
$K_{d+2}$-matroid which attains the maximum possible rank.

###  3.3 Maximality of the generic $C_{2}^{1}$-cofactor matroid

We show that ${\cal C}_{2,n}^{1}$ is the unique maximal element, with respect
to the weak order, in the set of all $K_{5}$-matroids on $E(K_{n})$. Since
every abstract $3$-rigidity matroid is a $K_{5}$-matroid, this immediately
implies Theorem 1.2.

######  Theorem 3.6.

The generic $C_{2}^{1}$-cofactor matroid ${\cal C}_{2,n}^{1}$ is the unique
maximal $K_{5}$-matroid on $E(K_{n})$ for all $n\geq 1$.

###### Proof.

The theorem is trivially true when $n\leq 5$ so we may assume that $n\geq 6$.
Let ${\cal M}$ be an arbitrary $K_{5}$-matroid on $E(K_{n})$ and $F\subseteq
E(K_{n})$ be an independent set in $\cal M$. We will show that $F$ is
independent in ${\cal C}_{2,n}^{1}$ by induction on $|F|$. We will abuse
notation throughout this proof and use the same letter for both a subgraph of
$K_{n}$ and its edge set.

Since ${\cal M}$ is a $K_{5}$-matroid, Lemma 3.5 implies that $|F|=r(F)\leq
3|V(F)|-6$, and hence there exists a vertex $v_{0}$ of degree at most five in
$F$. Let $N_{F}(v_{0})=\\{v_{1},\dots,v_{k}\\}$ (where $k$ is the degree of
$v_{0}$) and let $K$ be the complete graph on $N_{F}(v_{0})$.

Suppose $d_{F}(v_{0})\leq 3$. Since $F-v_{0}$ is independent in ${\cal M}$,
$F-v_{0}$ is independent in ${\cal C}^{1}_{2,n}$ by induction. Then $F$ is
independent in ${\cal C}^{1}_{2,n}$ by the $0$-extension property in Lemma
3.1. Hence we may suppose $d_{F}(v_{0})\in\\{4,5\\}$.

######  Claim 3.7.

${\rm cl}_{{\cal M}}(F-v_{0})\cap K$ does not contain a copy of $K_{4}$.

###### Proof.

Suppose, for a contradiction, that ${\rm cl}_{{\cal M}}(F-v_{0})$ contains a
copy of $K_{4}$. We may assume that ${\rm cl}_{{\cal M}}(F-v_{0})$ contains
$K(v_{1},v_{2},v_{3},v_{4})$. Let $e_{i}=v_{0}v_{i}$ for $1\leq i\leq 4$.
Since ${\cal M}$ is a $K_{5}$-matroid, $e_{4}\in\operatorname{cl}_{\cal
M}(F-v_{0}+e_{1}+e_{2}+e_{3})$. This contradicts the fact that $F$ is
independent in ${\cal M}$. ∎

Suppose that $d_{F}(v_{0})=4$. Claim 3.7 implies that $F-v_{0}+v_{1}v_{2}$ is
independent in ${\cal M}$ for two non-adjacent neighbors $v_{1}v_{2}$ of
$v_{0}$ in $F$. We can now apply induction to deduce that $F-v_{0}+v_{1}v_{2}$
is independent in ${\cal C}^{1}_{2,n}$ and then use the 1-extension property
in Lemma 3.1 to deduce that $F$ is independent in ${\cal C}^{1}_{2,n}$. Hence
we may assume that $d_{F}(v_{0})=5$.

######  Claim 3.8.

$K\not\subseteq{\rm cl}_{{\mathcal{M}}}(F-v_{0}+e)$ for all $e\in K$.

###### Proof.

Suppose, for a contradiction, that $K\subseteq{\rm
cl}_{{\mathcal{M}}}(F-v_{0}+e)$ for some $e\in K$. Then $F-v_{0}+e$ is
independent in ${\cal M}$ by Claim 3.7. Combining this with the fact ${\cal
M}$ is a $K_{5}$-matroid, we obtain $r_{\cal M}(F)\leq r_{\cal
M}(F-v_{0}+e)+3$. On the other hand, the fact that $F$ is independent in
${\cal M}$ tells us that $r_{\cal M}(F)=r_{\cal M}(F-v_{0})+5=r_{\cal
M}(F-v_{0}+e)+4$. This is a contradiction. ∎

Claims 3.7 and 3.8 imply that we can choose $e_{1},e_{2}\in K\setminus F$ such
that $(F-v_{0})+e_{1}+e_{2}$ is independent in ${\mathcal{M}}$. The induction
hypothesis now tells us that $(F-v_{0})+e_{1}+e_{2}$ is independent in ${\cal
C}^{1}_{2,n}$. If $e_{1},e_{2}$ have no common endvertices, then $F$ can be
obtained from $F-v_{0}+e_{1}+e_{2}$ by X-replacement and $F$ would be
independent in ${\cal C}^{1}_{2,n}$ by Lemma 3.1, a contradiction. Hence we
may suppose that $v_{1}$ is a common endvertex of $e_{1},e_{2}$. Claim 3.7 now
tells us that $F-v_{0}+e_{1}^{\prime}$ is independent in ${\cal M}$ for some
$e_{1}^{\prime}\in K(v_{2},v_{3},v_{4},v_{5})\setminus F$, and Claim 3.8 in
turn gives an edge $e_{2}^{\prime}\in K\setminus F$ such that
$F-v_{0}+e_{1}^{\prime}+e_{2}^{\prime}$ is independent in ${\cal M}$. Then
$F-v_{0}+e_{1}^{\prime}+e_{2}^{\prime}$ is independent in ${\cal C}^{1}_{2,n}$
by induction. Since $F$ can be obtained from $F-v_{0}+e_{1}+e_{2}$ and
$F-v_{0}+e_{1}^{\prime}+e_{2}^{\prime}$ by a double V-replacement, Theorem 3.3
tells us that $F$ is independent in ${\cal C}^{1}_{2,n}$. This contradiction
completes the proof. ∎

##  4 Double V-replacement

The remainder of the paper is dedicated to proving Theorem 3.3. Since we will
only be concerned with the $C_{2}^{1}$-cofactor matroid we will often suppress
specific mention of this matroid. In particular we will say that a set of
edges $F\subseteq E(K_{n})$ is independent if it is independent in ${\cal
C}^{1}_{2,n}$ and use $\operatorname{cl}(F)$ to denote the closure of $F$ in
${\cal C}^{1}_{2,n}$. We will continue to use the terms
$C^{1}_{2}$-independent and $C^{1}_{2}$-rigid for graphs.

In this section, we will formulate a special case of Theorem 3.3, Theorem 4.6
below, and then show that the general result will follow from this special
case. The proof of Theorem 4.6 is delayed until Sections 5 and 6.

We first need to establish a structural result for $C^{1}_{2}$-independent
graphs.

######  Lemma 4.1.

Let $H=(V,E)$ be a $C^{1}_{2}$-independent graph, $U=\\{v_{1},\dots,v_{5}\\}$
be a set of five vertices in $G$, and $K=K(U)$. Then at least one of the
following holds:

  * (i)

${\rm cl}(E)\cap K$ contains a copy of $K_{4}$.

  * (ii)

$K\subseteq{\rm cl}(E+e)$ for some edge $e\in K$.

  * (iii)

there are two non-adjacent edges $e_{1}$ and $e_{2}$ in $K$ such that
$H+e_{1}+e_{2}$ is $C^{1}_{2}$-independent.

  * (iv)

there are two adjacent edges $e_{1}$ and $e_{2}$ in $K$ such that
$H+e_{1}+e_{2}$ is $C^{1}_{2}$-independent and the common end-vertex of
$e_{1}$ and $e_{2}$ is incident to two edges in ${\rm cl}(E)\cap K$.

  * (v)

${\operatorname{cl}}(E)\cap K$ forms a star on five vertices, and ${\rm
cl}(E+e)\cap K$ contains no copy of $K_{4}$ for all $e\in K$.

###### Proof.

We assume that (i) - (iv) do not hold and prove that (v) must hold.

Since (iii) does not hold, we have:

for all $e=v_{i}v_{j}\in K\setminus{\rm cl}(E)$, ${\rm cl}(E+e)$ contains a
triangle on $U\setminus\\{v_{i},v_{j}\\}$.  (5)

######  Claim 4.2.

For all $e\in K$, ${\rm cl}(E+e)\cap K$ contains no copy of $K_{4}$.

###### Proof.

Since (i) does not occur, the claim follows if $e\in{\rm cl}(E)$. Thus we
suppose that $e\notin{\rm cl}(E)$, and hence $E+e$ is independent.

Relabeling if necessary, we may suppose $e=v_{1}v_{2}$. By (5), ${\rm
cl}(E+e)$ contains the triangle $K(v_{3},v_{4},v_{5})$ on
$\\{v_{3},v_{4},v_{5}\\}$. Since (ii) does not hold, ${\rm cl}(E+e)\cap K$
does not contain two copies of $K_{4}$ (since the union of two distinct copies
of $K_{4}$ on $U$ would form a $C_{2}^{1}$-rigid graph on $U$.) We consider
two cases.

_Case 1:_ Suppose that ${\rm cl}(E+e)\cap K$ contains a $K_{4}$ which includes
$e=v_{1}v_{2}$. By symmetry we may assume that this is a $K_{4}$ on
$\\{v_{1},v_{2},v_{3},v_{4}\\}$. Since ${\rm cl}(E+e)\cap K$ contains
$K(v_{3},v_{4},v_{5})$ and contains at most one $K_{4}$,
$v_{1}v_{5},v_{2}v_{5}\notin{\rm cl}(E+e)$. We will show that:

$\\{v_{2}v_{3},v_{2}v_{4}\\}\subset{\rm cl}(E).$ (6)

Suppose $v_{2}v_{3}\notin{\rm cl}(E)$. Since $v_{2}v_{3}\in{\rm
cl}(E+e)\setminus{\rm cl}(E)$, $E+v_{2}v_{3}$ is independent and ${\rm
cl}(E+e)={\rm cl}(E+v_{2}v_{3})$. Since $v_{1}v_{5}\notin{\rm cl}(E+e)$, this
in turn implies $v_{1}v_{5}\notin{\rm cl}(E+v_{2}v_{3})$. Hence
$E+v_{2}v_{3}+v_{1}v_{5}$ is independent, contradicting that (iii) does not
hold. Thus $v_{2}v_{3}\in{\rm cl}(E)$. The same argument for $v_{2}v_{4}$
implies (6).

Since $v_{2}v_{5}\notin{\rm cl}(E+e)$, $E+v_{1}v_{2}+v_{2}v_{5}$ is
independent. Combined with (6), this contradicts the assumption that (iv) does
not hold.

_Case 2:_ Suppose that ${\rm cl}(E+e)\cap K$ contains a $K_{4}$ which avoids
$e=v_{1}v_{2}$. By symmetry we may assume that this is a $K_{4}$ on
$\\{v_{1},v_{3},v_{4},v_{5}\\}$. Since ${\rm cl}(E+e)\cap K$ contains at most
one $K_{4}$, there is at most one edge from $v_{2}$ to
$\\{v_{3},v_{4},v_{5}\\}$ in ${\rm cl}(E+e)\cap K$ and we may assume by
symmetry that $v_{2}v_{4},v_{2}v_{5}\notin{\rm cl}(E+e)$. We will show that
this case cannot occur by showing that

all edges on $\\{v_{1},v_{3},v_{4},v_{5}\\}$ are in ${\rm cl}(E)$ (7)

and hence that (i) holds.

Suppose $v_{1}v_{3}\notin{\rm cl}(E)$. Then, since $v_{1}v_{3}\in{\rm
cl}(E+e)\setminus{\rm cl}(E)$, $E+v_{1}v_{3}$ is independent and ${\rm
cl}(E+v_{1}v_{2})={\rm cl}(E+v_{1}v_{3})$. Since $v_{2}v_{4}\notin{\rm
cl}(E+v_{1}v_{2})$, we have $v_{2}v_{4}\notin{\rm cl}(E+v_{1}v_{3})$. Hence
$E+v_{1}v_{3}+v_{2}v_{4}$ is independent and (iii) holds. This contradiction
implies that $v_{1}v_{3}\in{\rm cl}(E)$. The same argument holds for all the
other edges on $\\{v_{1},v_{3},v_{4},v_{5}\\}$ except $v_{4}v_{5}$. If
$v_{4}v_{5}\notin{\rm cl}(E)$ then, since $v_{4}v_{5}\in{\rm
cl}(E+v_{1}v_{2})\setminus{\rm cl}(E)$, $E+v_{4}v_{5}$ is independent and
${\rm cl}(E+v_{1}v_{2})={\rm cl}(E+v_{4}v_{5})$. This in turn implies
$v_{2}v_{4}\notin{\rm cl}(E+v_{4}v_{5})$, and $E+v_{2}v_{4}+v_{4}v_{5}$ is
independent. This and the fact $v_{1}v_{4},v_{3}v_{4}\in{\rm cl}(E)$
contradicts the assumption that (iv) does not hold. Hence
$v_{4}v_{5}\notin{\rm cl}(E)$ and (7) holds. ∎

Claim 4.2 implies that the second part of condition (v) in the statement
holds. It remains to show that ${\rm cl}(E)\cap K$ forms a star on $U$. This
will follow by combining Claims 4.4 and 4.5, below. We first derive an
auxiliary claim.

######  Claim 4.3.

Suppose that $E+v_{1}v_{2}$ is independent. Then ${\rm cl}(E)$ has at least
two edges on $\\{v_{3},v_{4},v_{5}\\}$.

###### Proof.

Recall that ${\rm cl}(E+v_{1}v_{2})$ contains a complete graph on
$\\{v_{3},v_{4},v_{5}\\}$ by (5).

We first consider the complete graph on $\\{v_{1},v_{2},v_{3},v_{4}\\}$. By
Claim 4.2, we may assume without loss of generality that
$v_{1}v_{3}\not\in{\rm cl}(E+v_{1}v_{2})$. If $v_{4}v_{5}\notin{\rm cl}(E)$,
then $v_{4}v_{5}\in{\rm cl}(E+v_{1}v_{2})\setminus{\rm cl}(E)$, and so ${\rm
cl}(E+v_{4}v_{5})={\rm cl}(E+v_{1}v_{2})$. Hence $v_{1}v_{3}\notin{\rm
cl}(E+v_{4}v_{5})$. This gives a contradiction as $E+v_{4}v_{5}+v_{1}v_{3}$
would be independent and (iii) would hold. Thus we obtain $v_{4}v_{5}\in{\rm
cl}(E)$.

We next consider the complete graph on $\\{v_{1},v_{2},v_{4},v_{5}\\}$. By
Claim 4.2, we may assume without loss of generality that either
$v_{1}v_{4}\notin{\rm cl}(E+v_{1}v_{2})$ or $v_{2}v_{4}\notin{\rm
cl}(E+v_{1}v_{2})$. If $v_{3}v_{5}\notin{\rm cl}(E)$, then $v_{3}v_{5}\in{\rm
cl}(E+v_{1}v_{2})\setminus{\rm cl}(E)$, and so ${\rm cl}(E+v_{1}v_{2})={\rm
cl}(E+v_{3}v_{5})$. Hence $v_{1}v_{4}\notin{\rm cl}(E+v_{3}v_{5})$ or
$v_{2}v_{4}\notin{\rm cl}(E+v_{3}v_{5})$ respectively. This gives a
contradiction as (iii) would hold. Thus we obtain $v_{3}v_{5}\in{\rm cl}(E)$.
∎

######  Claim 4.4.

For all $i$ with $1\leq i\leq 5$, $d_{{\rm cl}(E)\cap K}(v_{i})\geq 1$. And if
$d_{{\rm cl}(E)\cap K}(v_{i})=1$, then the vertex $v_{j}$ adjacent to $v_{i}$
in ${\rm cl}(E)\cap K$ satisfies $d_{{\rm cl}(E)\cap K}(v_{j})=4$.

###### Proof.

Suppose that $d_{{\rm cl}(E)\cap K}(v_{5})=0$. Since ${\rm cl}(E)$ has no copy
of $K_{4}$, we may assume $v_{1}v_{2}\not\in{\rm cl}(E)$. Then $E+v_{1}v_{2}$
is independent, and ${\rm cl}(E)$ has at most one edge on
$\\{v_{3},v_{4},v_{5}\\}$ since $d_{{\rm cl}(E)\cap K}(v_{5})=0$. This
contradicts Claim 4.3.

Suppose that $d_{{\rm cl}(E)\cap K}(v_{5})=1$. We may assume without loss of
generality that $v_{5}$ is adjacent to $v_{1}$ in ${\rm cl}(E)$. Suppose
further that ${\rm cl}(E)$ does not contain $v_{1}v_{2}$. Then $E+v_{1}v_{2}$
is independent. On the other hand, ${\rm cl}(E)$ has at most one edge on
$\\{v_{3},v_{4},v_{5}\\}$ because $v_{5}$ is incident only to $v_{1}$ in ${\rm
cl}(E)\cap K$. This again contradicts Claim 4.3. ∎

######  Claim 4.5.

${\rm cl}(E)\cap K$ is cycle free.

###### Proof.

Suppose that ${\rm cl}(E)\cap K$ contains a cycle of length five. By Claim 4.2
we may choose two chords $e_{1},e_{2}$ of this cycle such that $E+e_{1}+e_{2}$
is independent. This would contradict the assumption that (iii) and (iv) do
not hold since either $e_{1}$ and $e_{2}$ are non-adjacent or their common
end-vertex has degree two in ${\rm cl}(E)\cap K$.

Suppose that ${\rm cl}(E)\cap K$ contains a cycle of length four, say
$v_{1}v_{2}v_{3}v_{4}v_{1}$. Since ${\rm cl}(E)\cap K$ has no $K_{4}$, we may
suppose that $v_{1}v_{3}\notin{\rm cl}(E)$. Then Claim 4.2 implies that
$E+v_{1}v_{3}+v_{2}v_{4}$ is independent and (iii) holds, a contradiction.

Suppose that ${\rm cl}(E)\cap K$ contains a triangle, say
$K(v_{1},v_{2},v_{3})$. Claim 4.4 and the fact that ${\rm cl}(E)\cap K$
contains no cycle of length four tells us that there is exactly one edge in
${\rm cl}(E)\cap K$ from each of $v_{4},v_{5}$ to $\\{v_{1},v_{2},v_{3}\\}$,
and that both of these edges have a common end-vertex, say $v_{1}$. Hence
$E+v_{2}v_{4}$ is independent. We can now use (5) to deduce that
$v_{3}v_{5}\in{\rm cl}(E+v_{2}v_{4})$. Claim 4.2 now implies that
$v_{2}v_{5}\not\in{\rm cl}(E+v_{2}v_{4})$ and hence $E+v_{2}v_{4}+v_{2}v_{5}$
is independent. This gives a contradiction since $v_{2}$ has degree two in
${\rm cl}(E)\cap K$ and hence (iv) holds. ∎

Claims 4.4 and 4.5 imply that ${\rm cl}(E)\cap K$ forms a star on
$\\{v_{1},v_{2},\dots,v_{5}\\}$ and hence (v) holds. ∎

Let $G=(V,E)$ be a graph. A vertex $v_{0}$ in $G$ is said to be of type
$(\star)$ if

  * •

$v_{0}$ has degree five with
$N_{G}(v_{0})=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$,

  * •

$G-v_{0}+v_{1}v_{2}+v_{1}v_{3}$ and $G-v_{0}+v_{1}v_{3}+v_{3}v_{4}$ are both
$C_{2}^{1}$-rigid, and

  * •

${\rm cl}(E(G-v_{0}))\cap K(N_{G}(v_{0}))$ forms a star on five vertices
centered on $v_{5}$,

See Figure 4.

Figure 4: The double V-replacement that creates a vertex $v_{0}$ of type
($\star$). The dashed lines represent the edges in ${\rm cl}(E(G-v_{0}))\cap
K(N_{G}(v_{0}))$, which form a star on five vertices centered on $v_{5}$.

The following theorem implies that double V-replacement preserves minimal
$C_{2}^{1}$-rigidity in the special case when the new vertex is of type
$(\star)$.

######  Theorem 4.6.

Let $G=(V,E)$ be a graph with $|E|=3|V|-6$ and suppose that $G$ has a vertex
$v_{0}$ of type $(\star)$. Then $G$ is minimally $C_{2}^{1}$-rigid.

As noted above, we delay the proof of this theorem to Sections 5 and 6 and
instead use it to verify Theorem 3.3.

##### Proof of Theorem 3.3

Let $G=(V,E)$ be a graph that has a vertex $v_{0}$ of degree five, and let
$\\{e_{1},e_{2}\\}$ and $\\{e_{1}^{\prime},e_{2}^{\prime}\\}$ be two pairs of
adjacent edges on $N_{G}(v_{0})$. Suppose that $G-v_{0}+e_{1}+e_{2}$ and
$G-v_{0}+e_{1}^{\prime}+e_{2}^{\prime}$ are both $C^{1}_{2}$-independent, and
the common endvertex of $e_{1}$ and $e_{2}$ is distinct from that of
$e_{1}^{\prime}$ and $e_{2}^{\prime}$. Let
$N_{G}(v_{0})=\\{v_{1},\dots,v_{5}\\}$. We need to show that $G$ is
$C_{2}^{1}$-independent.

We apply Lemma 4.1 to $H:=G-v_{0}$ and $U:=N_{G}(v_{0})$. (Note that $H$ is
$C^{1}_{2}$-independent.) Neither (i) nor (ii) of Lemma 4.1 hold since
otherwise $G-v_{0}+e_{1}+e_{2}$ or $G-v_{0}+e_{1}^{\prime}+e_{2}^{\prime}$
would be dependent. If (iii) holds, then we can construct $G$ from a
$C^{1}_{2}$-independent graph by X-replacement, and hence $G$ is
$C^{1}_{2}$-independent by Lemma 3.1. Similarly, if (iv) holds, then $G$ can
be constructed from a $C^{1}_{2}$-independent graph by a V-replacement
satisfying the hypotheses of Lemma 3.2 so is $C^{1}_{2}$-independent. Hence we
may assume (v) of Lemma 4.1 holds, and, without loss of generality, that ${\rm
cl}(E(H))\cap K(U)$ forms a star whose center is $v_{5}$. Then
$E(H)+v_{1}v_{2}$ and $E(H)+v_{3}v_{4}$ are both independent. If
$v_{3}v_{4}\notin{\rm cl}(E(H)+v_{1}v_{2})$, then $G$ can be obtained from the
$C^{1}_{2}$-independent graph $H+v_{1}v_{2}+v_{3}v_{4}$ by X-replacement.
Hence we may assume that $v_{3}v_{4}\in{\rm cl}(E(H)+v_{1}v_{2})$, and thus
${\rm cl}(E(H)+v_{1}v_{2})={\rm cl}(E(H)+v_{3}v_{4})$ by the independence of
$H+v_{3}v_{4}$. Since (v) of Lemma 4.1 holds, we may further suppose that
$v_{1}v_{3}\notin{\rm cl}(E(H)+v_{1}v_{2})$. Therefore both
$H+v_{1}v_{2}+v_{1}v_{3}$ and $H+v_{3}v_{4}+v_{1}v_{3}$ are
$C^{1}_{2}$-independent.

Let $k=3|V|-6-|E|$. We complete the proof by induction on $k$. If $k=0$ then
$H+v_{1}v_{2}+v_{1}v_{3}$ and $H+v_{3}v_{4}+v_{1}v_{3}$ are both minimally
$C_{2}^{1}$-rigid, and $v_{0}$ is of type $(\star)$. Theorem 4.6 now implies
that $G$ is minimally $C_{2}^{1}$-rigid.

For the induction step, we assume that $k>0$. Since ${\rm
cl}(E(H)+v_{1}v_{2})={\rm cl}(E(H)+v_{3}v_{4})$, we have ${\rm
cl}(E(H)+v_{1}v_{2}+v_{1}v_{3})={\rm cl}(E(H)+v_{3}v_{4}+v_{1}v_{3})$. As
$H+v_{1}v_{2}+v_{1}v_{3}$ is a $k$-dof graph with $k>0$, there is an edge
$f\in K(V-v_{0})$ such that $H+v_{1}v_{2}+v_{1}v_{3}+f$ and
$H+v_{3}v_{4}+v_{1}v_{3}+f$ are both $C^{1}_{2}$-independent. Applying the
induction hypothesis to $H+f$, we find that $G+f$ is $C^{1}_{2}$-independent.
Therefore $G$ is $C^{1}_{2}$-independent. ∎

##  5 Bad $C_{2}^{1}$-Motions

In this section, we show that if Theorem 4.6 does not hold for some graph $G$,
then every generic realization of $G$ in $\mathbb{R}^{2}$ has a special kind
of motion, and derive some properties of such ‘bad’ motions. We use these
properties in Section 6, to prove that no generic framework can have a bad
motion.

The following notation will be used throughout the remainder of this paper.
Suppose $p_{i}=(x_{i},y_{i})$ is a point in the plane for $i=0,1,2,3$. For any
three of these points, we let

$\Delta(p_{i},p_{j},p_{k})=\begin{vmatrix}x_{i}&y_{i}&1\\\ x_{j}&y_{j}&1\\\
x_{k}&y_{k}&1\end{vmatrix},$

which is twice the signed area of the triangle defined by the three points.
The formula for the determinant of a Vandermonde matrix implies that

$\displaystyle\left|\begin{array}[]{c}D(p_{0},p_{1})\\\ D(p_{0},p_{2})\\\
D(p_{0},p_{3})\end{array}\right|$
$\displaystyle=-\left|\begin{array}[]{ccc}x_{0}&y_{0}&1\\\ x_{1}&y_{1}&1\\\
x_{2}&y_{2}&1\end{array}\right|\left|\begin{array}[]{ccc}x_{0}&y_{0}&1\\\
x_{2}&y_{2}&1\\\
x_{3}&y_{3}&1\end{array}\right|\left|\begin{array}[]{ccc}x_{0}&y_{0}&1\\\
x_{3}&y_{3}&1\\\ x_{1}&y_{1}&1\end{array}\right|$ (20)
$\displaystyle=-\Delta(p_{0},p_{1},p_{2})\Delta(p_{0},p_{2},p_{3})\Delta(p_{0},p_{3},p_{1}).$
(21)

See, e.g., [19, page 15] for further details.

###  5.1 Bad local behavior

The following key lemma states that if Theorem 4.6 does not hold for some
vertex $v_{0}$ of type ($\star$) in a graph $G$, then every generic framework
$(G,{\bm{p}})$ has a non-trivial $C_{2}^{1}$-motion ${\bm{q}}$ with the
property that each coordinate of ${\bm{q}}(v_{i})$, for
$v_{i}\in\hat{N}_{G}(v_{0})$, can be expressed as a polynomial in the
coordinates of the points ${\bm{p}}(v_{j})$, for $v_{j}\in\hat{N}_{G}(v_{0})$.
We note that the precise formulae of Lemma 5.1 are not important in the
remaining proof, and only the fact that each coordinate is written as a
polynomial in the coordinates of
${\bm{p}}(v_{0}),{\bm{p}}(v_{1}),\dots,{\bm{p}}(v_{5})$ will be important.

######  Lemma 5.1.

Let $(G,{\bm{p}})$ be a generic framework, $v_{0}$ be a vertex of type
$(\star)$ in $G$ with $N_{G}(v_{0})=\\{v_{1},\dots,v_{5}\\}$, $H=G-v_{0}$ and
${\bm{p}}|_{H}$ be the restriction of ${\bm{p}}$ to $H$. Suppose that $G$ is
not $C_{2}^{1}$-rigid. Then there exist non-trivial $C_{2}^{1}$-motions
${\bm{q}}_{1}$ of $(H+v_{1}v_{2},{\bm{p}}|_{H})$ and ${\bm{q}}_{2}$ of
$(H+v_{1}v_{3},{\bm{p}}|_{H})$ satisfying

$\displaystyle{\bm{q}}_{1}(v_{1})$
$\displaystyle={\bm{q}}_{1}(v_{2})={\bm{q}}_{1}(v_{5})=0,$
$\displaystyle{\bm{q}}_{1}(v_{3})$
$\displaystyle=\Delta({\bm{p}}(v_{1}),{\bm{p}}(v_{2}),{\bm{p}}(v_{3}))D(v_{3},v_{4})\times
D(v_{3},v_{5}),$ $\displaystyle{\bm{q}}_{1}(v_{4})$
$\displaystyle=\Delta({\bm{p}}(v_{1}),{\bm{p}}(v_{2}),{\bm{p}}(v_{4}))D(v_{3},v_{4})\times
D(v_{4},v_{5}),$

and

$\displaystyle{\bm{q}}_{2}(v_{1})$
$\displaystyle={\bm{q}}_{2}(v_{3})={\bm{q}}_{2}(v_{5})=0,$
$\displaystyle{\bm{q}}_{2}(v_{2})$
$\displaystyle=\Delta({\bm{p}}(v_{1}),{\bm{p}}(v_{3}),{\bm{p}}(v_{2}))D(v_{2},v_{4})\times
D(v_{2},v_{5}),$ $\displaystyle{\bm{q}}_{2}(v_{4})$
$\displaystyle=\Delta({\bm{p}}(v_{1}),{\bm{p}}(v_{3}),{\bm{p}}(v_{4}))D(v_{2},v_{4})\times
D(v_{4},v_{5}),$

where $\times$ denotes the cross product of two vectors. Moreover, $G$ has a
non-trivial motion ${\bm{q}}$ such that
${\bm{q}}|_{V-v_{0}}=\alpha{\bm{q}}_{1}+\beta{\bm{q}}_{2}$, where

$\displaystyle\alpha=\begin{vmatrix}D(v_{0},v_{2})\\\ D(v_{2},v_{4})\\\
D(v_{2},v_{5})\end{vmatrix}\begin{vmatrix}D(v_{0},v_{3})\\\ D(v_{0},v_{1})\\\
D(v_{0},v_{5})\end{vmatrix},\quad\beta=-\begin{vmatrix}D(v_{0},v_{3})\\\
D(v_{3},v_{4})\\\ D(v_{3},v_{5})\end{vmatrix}\begin{vmatrix}D(v_{0},v_{2})\\\
D(v_{0},v_{1})\\\ D(v_{0},v_{5})\end{vmatrix},$

and ${\bm{q}}(v_{0})$ is given by

${\bm{q}}(v_{0})=\Delta({\bm{p}}(v_{1}),{\bm{p}}(v_{2}){\bm{p}}(v_{3}))\begin{vmatrix}D(v_{0},v_{3})\\\
D(v_{3},v_{4})\\\ D(v_{3},v_{5})\end{vmatrix}\begin{vmatrix}D(v_{0},v_{2})\\\
D(v_{2},v_{4})\\\ D(v_{2},v_{5})\end{vmatrix}D(v_{0},v_{1})\times
D(v_{0},v_{5}).$

###### Proof.

For simplicity, put $D_{i,j}=D(v_{i},v_{j})$ and
$\Delta_{i,j,k}=\Delta({\bm{p}}(v_{i}),{\bm{p}}(v_{j}),{\bm{p}}(v_{k}))$.

Since $v_{0}$ is of type $(\star)$ in $G$,
$(H+v_{1}v_{2}+v_{1}v_{3},{\bm{p}}|_{H})$ and
$(H+v_{1}v_{3}+v_{3}v_{4},{\bm{p}}|_{H})$ are both $C_{2}^{1}$-rigid. Also
${\rm cl}(E(H))$ forms a star on $N_{G}(v_{0})$ centered at $v_{5}$. We first
prove a result concerning the $C_{2}^{1}$-motions of $(H,{\bm{p}}|_{H})$.

######  Claim 5.2.

There exist non-trivial $C_{2}^{1}$-motions ${\bm{q}}_{1}$ of
$(H+v_{1}v_{2},{\bm{p}}|_{H})$ and ${\bm{q}}_{2}$ of
$(H+v_{1}v_{3},{\bm{p}}|_{H})$ such that: (a)
${\bm{q}}_{1}(v_{1})={\bm{q}}_{1}(v_{2})={\bm{q}}_{1}(v_{5})=0$,
$D_{3,4}\cdot[{\bm{q}}_{1}(v_{3})-{\bm{q}}_{1}(v_{4})]=0$, and
$D_{1,3}\cdot{\bm{q}}_{1}(v_{3})\neq 0$; (b)
${\bm{q}}_{2}(v_{1})={\bm{q}}_{2}(v_{3})={\bm{q}}_{2}(v_{5})=0$,
$D_{2,4}\cdot[{\bm{q}}_{2}(v_{2})-{\bm{q}}_{2}(v_{4})]=0$, and
$D_{1,2}\cdot{\bm{q}}_{2}(v_{2})\neq 0$; (c)
$Z(H,{\bm{p}}|_{H})=Z_{0}(H,{\bm{p}}|_{H})\oplus\langle{\bm{q}}_{1},{\bm{q}}_{2}\rangle$.

###### Proof.

Since ${\rm cl}(E(H))$ forms a star on $N_{G}(v_{0})$ centered at $v_{5}$,
${\rm cl}(E(H)+v_{1}v_{2})$ contains the triangle $K(v_{1},v_{2},v_{5})$.
Since $G$ contains a $1$-extension of $H+v_{1}v_{2}$ and is not
$C_{2}^{1}$-rigid, $H+v_{1}v_{2}$ is not $C_{2}^{1}$-rigid. Hence we can
choose a non-trivial motion ${\bm{q}}_{1}$ of $(H+v_{1}v_{2},{\bm{p}}|_{H})$
such that ${\bm{q}}_{1}(v_{1})={\bm{q}}_{1}(v_{2})={\bm{q}}_{1}(v_{5})=0$ (by
pinning the triangle on $\\{v_{1},v_{2},v_{5}\\}$). The fact that
$(H+v_{1}v_{2}+v_{1}v_{3},{\bm{p}}|_{H})$ is $C_{2}^{1}$-rigid implies that
$D_{1,3}\cdot[{\bm{q}}_{1}(v_{3})-{\bm{q}}_{1}(v_{1})]=D_{1,3}\cdot{\bm{q}}_{1}(v_{3})\neq
0$. If $D_{3,4}\cdot[{\bm{q}}_{1}(v_{3})-{\bm{q}}_{1}(v_{4})]\neq 0$ then
$H+v_{1}v_{2}+v_{3}v_{4}$ would be $C_{2}^{1}$-rigid, and $G$ would also be
$C_{2}^{1}$-rigid since it can be obtained from $H+v_{1}v_{2}+v_{3}v_{4}$ by
an X-replacement. Thus
$D_{3,4}\cdot[{\bm{q}}_{1}(v_{3})-{\bm{q}}_{1}(v_{4})]=0$. This completes the
proof of (a). Part (b) can be proved analogously.

The facts that $D_{1,2}\cdot[{\bm{q}}_{1}(v_{1})-{\bm{q}}_{1}(v_{2})]=0\neq
D_{1,2}\cdot[{\bm{q}}_{2}(v_{1})-{\bm{q}}_{2}(v_{2})]$ and
$D_{1,3}\cdot[{\bm{q}}_{1}(v_{1})-{\bm{q}}_{1}(v_{3})]\neq
0=D_{1,3}\cdot[{\bm{q}}_{2}(v_{1})-{\bm{q}}_{2}(v_{3})]$ imply that
${\bm{q}}_{1},{\bm{q}}_{2}$ are linearly independent and can be extended to a
base of $Z(H,{\bm{p}}|_{H})$ by adding the vectors in a base of
$Z_{0}(H,{\bm{p}}|_{H})$. Hence
$Z(H,{\bm{p}}|_{H})=Z_{0}(H,{\bm{p}}|_{H})\oplus\langle{\bm{q}}_{1},{\bm{q}}_{2}\rangle$.
∎

######  Claim 5.3.

There exists a non-trivial $C_{2}^{1}$-motion ${\bm{q}}$ of $(G,{\bm{p}})$
such that ${\bm{q}}|_{H}=\alpha{\bm{q}}_{1}+\beta{\bm{q}}_{2}$ for some
$\alpha,\beta\in{\mathbb{R}}$ with $\beta\neq 0$.

###### Proof.

Since $G$ is not $C_{2}^{1}$-rigid, we may choose a non-trivial
$C_{2}^{1}$-motion ${\bm{q}}$ of $(G,{\bm{p}})$. Since $d_{G}(v_{0})=5$,
${\bm{q}}|_{H}$ is a non-trivial $C_{2}^{1}$-motion of $(H,{\bm{p}}|_{H})$. By
Claim 5.2(c),
${\bm{q}}|_{H}={\bm{q}}_{0}+\alpha{\bm{q}}_{1}+\beta{\bm{q}}_{2}$ for some
${\bm{q}}_{0}\in Z_{0}(H,{\bm{p}}|_{H})$ and $\alpha,\beta\in{\mathbb{R}}$. We
may choose $\tilde{\bm{q}}\in Z_{0}(G,{\bm{p}})$ such that
$\tilde{\bm{q}}|_{H}={\bm{q}}_{0}$. Then
$\hat{\bm{q}}={\bm{q}}-\tilde{\bm{q}}$ is a non-trivial $C_{2}^{1}$-motion of
$(G,{\bm{p}})$ and $\hat{\bm{q}}|_{H}=\alpha{\bm{q}}_{1}+\beta{\bm{q}}_{2}$.
Since $(G+v_{1}v_{2},{\bm{p}})$ can be obtained from
$(H+v_{1}v_{2}+v_{1}v_{3},{\bm{p}}|_{H})$ by first performing a 1-extension
operation and then adding the edge $v_{0}v_{5}$, $(G+v_{1}v_{2},{\bm{p}})$ is
$C_{2}^{1}$-rigid. This tells us that
$D_{1,2}\cdot[\hat{\bm{q}}(v_{1})-\hat{\bm{q}}(v_{2})]\neq 0$ and hence
$\beta\neq 0$. ∎

Let $\alpha,\beta$ be as described in Claim 5.3, and put
$\gamma=\alpha/\beta$. For all $1\leq i\leq 5$, $G$ contains the edge
$v_{0}v_{i}$, and so $D_{0,i}\cdot[{\bm{q}}(v_{0})-{\bm{q}}(v_{i})]=0$. Since
${\bm{q}}(v_{i})=\alpha{\bm{q}}_{1}(v_{i})+\beta{\bm{q}}_{2}(v_{i})$ for
$1\leq i\leq 5$, we obtain the system of equations

$D_{0,i}\cdot[{\bm{q}}(v_{0})/\beta-\gamma{\bm{q}}_{1}(v_{i})]=D_{0,i}\cdot{\bm{q}}_{2}(v_{i})\mbox{
for $1\leq i\leq 5$}.$

Putting ${\bm{q}}(v_{0})/\beta=(a_{0},b_{0},c_{0})$, and using the facts that
${\bm{q}}_{1}$ is zero on $v_{1},v_{2},v_{5}$ and ${\bm{q}}_{2}$ is zero on
$v_{1},v_{3},v_{5}$, we may rewrite this system as the matrix equation

$\left(\begin{array}[]{ccc}D_{0,1}&0\\\ D_{0,2}&0\\\
D_{0,3}&-D_{0,3}\cdot{\bm{q}}_{1}(v_{3})\\\
D_{0,4}&-D_{0,4}\cdot{\bm{q}}_{1}(v_{4})\\\
D_{0,5}&0\end{array}\right)\left(\begin{array}[]{c}a_{0}\\\ b_{0}\\\ c_{0}\\\
\gamma\end{array}\right)=\left(\begin{array}[]{c}0\\\
D_{0,2}\cdot{\bm{q}}_{2}(v_{2})\\\ 0\\\ D_{0,4}\cdot{\bm{q}}_{2}(v_{4})\\\
0\end{array}\right)\,.$ (22)

Since this equation has a solution for $a_{0},b_{0},c_{0},\gamma$ we have

$\left|\begin{array}[]{ccc}D_{0,1}&0&0\\\
D_{0,2}&0&D_{0,2}\cdot{\bm{q}}_{2}(v_{2})\\\
D_{0,3}&-D_{0,3}\cdot{\bm{q}}_{1}(v_{3})&0\\\
D_{0,4}&-D_{0,4}\cdot{\bm{q}}_{1}(v_{4})&D_{0,4}\cdot{\bm{q}}_{2}(v_{4})\\\
D_{0,5}&0&0\end{array}\right|=0\,.$ (23)

Let ${\bm{p}}(v_{0})=(x_{0},y_{0})$. The left hand side of (23) is a
polynomial in $x_{0},y_{0}$ with coefficients in
$\mathbb{Q}({\bm{p}}|_{H},{\bm{q}}_{1},{\bm{q}}_{2})$. Since it is equal to
zero for all generic values of $x_{0},y_{0}$, each coefficient is zero. This
implies that (23) will hold for all values of $x_{0}$ and $y_{0}$, including
non-generic choices of ${\bm{p}}(v_{0})$.

######  Claim 5.4.

$D_{3,4}\cdot{\bm{q}}_{1}(v_{3})=0.$

###### Proof.

We choose ${\bm{p}}(v_{0})$ to be a point on the interior of the line segment
joining ${\bm{p}}(v_{3})$ and ${\bm{p}}(v_{4})$. Then $D_{0,3}$ and $D_{0,4}$
are scalar multiples of $D_{3,4}$. We can now use elementary row and column
operations to convert (23) to

$\left|\begin{array}[]{ccc}D_{0,1}&0&0\\\
D_{0,2}&0&D_{0,2}\cdot{\bm{q}}_{2}(v_{2})\\\
D_{3,4}&D_{3,4}\cdot{\bm{q}}_{1}(v_{3})&0\\\
0&D_{3,4}\cdot({\bm{q}}_{1}(v_{4})-{\bm{q}}_{1}(v_{3}))&D_{3,4}\cdot{\bm{q}}_{2}(v_{4})\\\
D_{0,5}&0&0\end{array}\right|=0.\,$ (24)

Since $D_{3,4}\cdot({\bm{q}}_{1}(v_{4})-{\bm{q}}_{1}(v_{3}))=0$ by Claim
5.2(a), this gives

$\left|\begin{array}[]{ccc}D_{0,1}&0&0\\\
D_{0,2}&0&D_{0,2}\cdot{\bm{q}}_{2}(v_{2})\\\
D_{3,4}&D_{3,4}\cdot{\bm{q}}_{1}(v_{3})&0\\\
0&0&D_{3,4}\cdot{\bm{q}}_{2}(v_{4})\\\ D_{0,5}&0&0\end{array}\right|=0.\,$
(25)

Hence

$\left|\begin{array}[]{c}D_{0,1}\\\ D_{0,2}\\\
D_{0,5}\end{array}\right|(D_{3,4}\cdot{\bm{q}}_{1}(v_{3}))\,(D_{3,4}\cdot{\bm{q}}_{2}(v_{4}))=0.$
(26)

As long as ${\bm{p}}(v_{0})$ is generic on the line through ${\bm{p}}(v_{3})$
and ${\bm{p}}(v_{4})$, the first term is non-zero. Since ${\bm{q}}_{2}$ is a
non-trivial $C_{2}^{1}$-motion of $(H+v_{1}v_{3},{\bm{p}}|_{H})$ and
$(H+v_{1}v_{3}+v_{3}v_{4},{\bm{p}}|_{H})$ is $C_{2}^{1}$-rigid, we also have
$D_{3,4}\cdot{\bm{q}}_{2}(v_{4})=D_{3,4}\cdot({\bm{q}}_{2}(v_{4})-{\bm{q}}_{2}(v_{3}))\neq
0$. Hence (26) gives $D_{3,4}\cdot{\bm{q}}_{1}(v_{3})=0$. ∎

Since the edge $v_{3}v_{5}$ exists in ${\rm cl}(E(H))$ and
${\bm{q}}_{1}(v_{5})=0$, we also have

$D_{3,5}\cdot{\bm{q}}_{1}(v_{3})=0.$ (27)

Claim 5.4 and (27) imply that ${\bm{q}}_{1}(v_{3})$ is a vector in the
orthogonal complement of the span of $D_{3,4}$ and $D_{3,5}$. Hence, scaling
${\bm{q}}_{1}$ appropriately, we may assume that

${\bm{q}}_{1}(v_{3})=\Delta_{1,2,3}\,D_{3,4}\times D_{3,5}.$ (28)

By an analogous argument on the line through ${\bm{p}}(v_{2})$ and
${\bm{p}}(v_{4})$, we obtain

${\bm{q}}_{2}(v_{2})=\Delta_{1,3,2}D_{2,4}\times D_{2,5}.$ (29)

We next calculate ${\bm{q}}_{1}(v_{4})$. Since the edge $v_{4}v_{5}$ exists in
${\rm cl}(E(H))$ and ${\bm{q}}_{1}(v_{5})=0$, we have
$D_{4,5}\cdot{\bm{q}}_{1}(v_{4})=0$. Also the edge $v_{3}v_{4}$ exists in
${\rm cl}(E(H)+v_{1}v_{2})$, since otherwise we could perform an X-replacement
on $H+v_{1}v_{2}+v_{3}v_{4}$ and deduce that $G$ is $C_{2}^{1}$-rigid. Hence
$D_{3,4}\cdot({\bm{q}}_{1}(v_{4})-{\bm{q}}_{1}(v_{3}))=0$. Since
$D_{3,4}\cdot{\bm{q}}_{1}(v_{3})=0$ by Claim 5.4, we have
$D_{3,4}\cdot{\bm{q}}_{1}(v_{4})=0$. Thus ${\bm{q}}_{1}(v_{4})$ is in the
orthogonal complement of the span of $D_{4,5}$ and $D_{3,4}$, and
${\bm{q}}_{1}(v_{4})=sD_{3,4}\times D_{4,5}$ for some $s\in\mathbb{R}$. The
next claim determines the value of $s$:

######  Claim 5.5.

$s=\Delta_{1,2,4}$.

###### Proof.

We put ${\bm{p}}(v_{0})$ on the interior of the line segment joining
${\bm{p}}(v_{1})$ and ${\bm{p}}(v_{2})$. Then $D_{0,1}$ is a scalar multiple
of $D_{0,2}$. With this choice of ${\bm{p}}(v_{0})$, we may expand the
determinant in (23) to obtain

$\left|\begin{array}[]{c}D_{0,1}\\\ D_{0,5}\\\
D_{0,3}\end{array}\right|(D_{0,4}\cdot{\bm{q}}_{1}(v_{4}))(D_{0,2}\cdot{\bm{q}}_{2}(v_{2}))-\left|\begin{array}[]{c}D_{0,1}\\\
D_{0,5}\\\
D_{0,4}\end{array}\right|(D_{0,3}\cdot{\bm{q}}_{1}(v_{3}))(D_{0,2}\cdot{\bm{q}}_{2}(v_{2}))=0.$
(30)

We may use the fact that $D_{1,2}\cdot{\bm{q}}_{2}(v_{2})\neq 0$ by Claim
5.2(b) to deduce that $D_{0,2}\cdot{\bm{q}}_{2}(v_{2})\neq 0$ and then rewrite
(30) as

$\left|\begin{array}[]{c}D_{0,1}\\\ D_{0,5}\\\
D_{0,3}\end{array}\right|(D_{0,4}\cdot{\bm{q}}_{1}(v_{4}))-\left|\begin{array}[]{c}D_{0,1}\\\
D_{0,5}\\\ D_{0,4}\end{array}\right|(D_{0,3}\cdot{\bm{q}}_{1}(v_{3}))=0.$ (31)

Using ${\bm{q}}_{1}(v_{4})=sD_{3,4}\times D_{4,5}$, and substituting
${\bm{q}}_{1}(v_{3})$ with (28), we obtain

$s=\frac{\left|\begin{array}[]{c}D_{0,1}\\\ D_{0,5}\\\
D_{0,4}\end{array}\right|\left|\begin{array}[]{c}D_{0,3}\\\ D_{3,4}\\\
D_{3,5}\end{array}\right|}{\left|\begin{array}[]{c}D_{0,1}\\\ D_{0,5}\\\
D_{0,3}\end{array}\right|\left|\begin{array}[]{c}D_{0,4}\\\ D_{3,4}\\\
D_{4,5}\end{array}\right|}\Delta_{1,2,3}.$ (32)

By using the identity (21) and the fact $D_{i,j}=D_{j,i}$, (32) becomes

$s=\frac{\Delta_{0,1,5}\Delta_{0,5,4}\Delta_{0,4,1}\Delta_{3,0,4}\Delta_{3,4,5}\Delta_{3,5,0}}{\Delta_{0,1,5}\Delta_{0,5,3}\Delta_{0,3,1}\Delta_{4,0,3}\Delta_{4,3,5}\Delta_{4,5,0}}\Delta_{1,2,3}=\frac{\Delta_{0,4,1}}{\Delta_{0,3,1}}\Delta_{1,2,3}.$
(33)

Finally since ${\bm{p}}(v_{0})$ is on the interior of the line segment joining
${\bm{p}}(v_{1})$ and ${\bm{p}}(v_{2})$, we get

$s=\frac{\Delta_{0,4,1}}{\Delta_{0,3,1}}\Delta_{1,2,3}=\frac{\Delta_{1,2,4}}{\Delta_{1,2,3}}\Delta_{1,2,3}=\Delta_{1,2,4}.\qed$

This completes the derivation of the formula for ${\bm{q}}_{1}$ in the
statement of the lemma. The formula for ${\bm{q}}_{2}$ can be obtained using a
symmetric argument by changing the role of $v_{2}$ and $v_{3}$.

It remains to compute ${\bm{q}}(v_{0})$. By (22), ${\bm{q}}(v_{0})/\beta$ is
in the orthogonal complement of the span of $D_{0,1}$ and $D_{0,5}$. Hence
${\bm{q}}(v_{0})/\beta=kD_{0,1}\times D_{0,5}$ for some $k\in\mathbb{R}$. By
the second equation in (22), we also have
$D_{0,2}\cdot{\bm{q}}_{2}(v_{2})=D_{0,2}\cdot({\bm{q}}(v_{0})/\beta)=kD_{0,2}\cdot(D_{0,1}\times
D_{0,5})$. Combining this with (29), we get

$k=\Delta_{1,3,2}\frac{D_{0,2}\cdot(D_{2,4}\times
D_{2,5})}{D_{0,2}\cdot(D_{0,1}\times D_{0,5})}.$ (34)

By the third equation in (22),
$(D_{0,3}\cdot{\bm{q}}_{1}(v_{3}))\gamma=D_{0,3}\cdot{\bm{q}}(v_{0})/\beta=kD_{0,3}\cdot(D_{0,1}\times
D_{0,5})$. Hence by (34) and (28) we get

$\displaystyle\frac{\alpha}{\beta}=\gamma$
$\displaystyle=\frac{kD_{0,3}\cdot(D_{0,1}\times
D_{0,5})}{D_{0,3}\cdot{\bm{q}}_{1}(v_{3})}=\frac{\Delta_{1,3,2}D_{02}\cdot(D_{24}\times
D_{25})D_{03}\cdot(D_{01}\times
D_{05})}{\Delta_{1,2,3}D_{03}\cdot(D_{34}\times
D_{35})D_{02}\cdot(D_{01}\times D_{05})}$
$\displaystyle=-\frac{\left|\begin{array}[]{c}D_{0,2}\\\ D_{2,4}\\\
D_{2,5}\end{array}\right|\left|\begin{array}[]{c}D_{0,3}\\\ D_{0,1}\\\
D_{0,5}\end{array}\right|}{\left|\begin{array}[]{c}D_{0,3}\\\ D_{3,4}\\\
D_{3,5}\end{array}\right|\left|\begin{array}[]{c}D_{0,2}\\\ D_{0,1}\\\
D_{0,5}\end{array}\right|}.$

By scaling ${\bm{q}}$ appropriately, we may take

$\alpha=\left|\begin{array}[]{c}D_{0,2}\\\ D_{2,4}\\\
D_{2,5}\end{array}\right|\left|\begin{array}[]{c}D_{0,3}\\\ D_{0,1}\\\
D_{0,5}\end{array}\right|\mbox{ and }\beta=-\left|\begin{array}[]{c}D_{0,3}\\\
D_{3,4}\\\ D_{3,5}\end{array}\right|\left|\begin{array}[]{c}D_{0,2}\\\
D_{0,1}\\\ D_{0,5}\end{array}\right|.$

Since ${\bm{q}}(v_{0})=\beta kD_{0,1}\times D_{0,5}$, we can now use (34) to
obtain the formula for ${\bm{q}}(v_{0})$ given in the statement of the lemma.
∎

###  5.2 Bad motions and proof of Theorem 4.6

Let $(G,{\bm{p}})$ be a generic framework and $v_{0}$ be a vertex of type
$(\star)$ in $G$ with $N_{G}(v_{0})=\\{v_{1},\dots,v_{5}\\}$. Lemma 5.1 shows
that, if $G$ is not $C_{2}^{1}$-rigid, then $(G,{\bm{p}})$ is a 1-dof
framework and has a non-trivial motion ${\bm{q}}$ with the property that the
coordinates of ${\bm{q}}$ at each vertex of $\hat{N}_{G}(v_{0})$ are three
polynomials in the coordinates of ${\bm{p}}(\hat{N}_{G}(v_{0}))$ with
coefficients in ${\mathbb{Q}}$. This seems unlikely as the graph on
$N_{G}(v_{0})$ induced by $\operatorname{cl}(E(G-v_{0}))$ is a star on the
five vertices (since $v_{0}$ is of type $(\star)$), which has a large degree
of freedom as a subframework. Our goal is to give a rigorous proof that this
cannot happen. The following concepts will be useful for this purpose.

Let $G=(V,E)$ be a graph with $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$. For
$U\subseteq V$, let

$b:U\to{\mathbb{Q}}[X_{1},Y_{1},X_{2},Y_{2},\ldots,X_{n},Y_{n}]^{3}$

be a map which associates a 3-tuple $b_{i}$ of polynomials in $2n$ variables
to each $v_{i}\in U$.

For a given framework $(G,{\bm{p}})$ with ${\bm{p}}(v_{i})=(x_{i},y_{i})$ for
all $1\leq i\leq n$, the substitution of $(X_{i},Y_{i})$ with $(x_{i},y_{i})$
in $b_{i}$ for all $1\leq i\leq n$ gives a vector $b_{i}({\bm{p}})$ in
${\mathbb{R}}^{3}$ for each $v_{i}\in U$. We say that a $C_{2}^{1}$-motion
${\bm{q}}$ of $(G,{\bm{p}})$ is a $b$-motion if
${\bm{q}}(v_{i})=b_{i}({\bm{p}})$ for all $v_{i}\in U$.

The following lemma states that the property of having a $b$-motion is stable
over a large set $S$ of realisations. (In particular, it will imply that this
property is generic). Since we will need the realisations in $S$ to satisfy
the hypotheses of Lemma 2.2 it will be convenient to say that the realisation
${\bm{p}}$ is non-degenerate on $U$ if there exist three distinct vertices in
$U$ which have distinct ‘$y$-coordinates’ in $(G,{\bm{p}})$.

######  Lemma 5.6.

Let $G=(V,E)$ be a $C_{2}^{1}$-independent graph with
$V=\\{v_{1},\dots,v_{n}\\}$, $U\subseteq V$, $F\subseteq K(U)$, and
$S=\\{{\bm{p}}:\mbox{$(G+F,{\bm{p}})$ is minimally $C_{2}^{1}$-rigid and
${\bm{p}}$ is non-degenerate on $U$}\\}.$ Suppose that
$b:U\to{\mathbb{Q}}[X_{1},Y_{1},\ldots,X_{n},Y_{n}]^{3}$ and $(G,{\bm{p}})$
has a $b$-motion for some generic ${\bm{p}}$. Then $(G,{\bm{p}})$ has a
$b$-motion for all ${\bm{p}}\in S$.

Lemma 5.6 can be understood as follows. Since each entry of $C(G,{\bm{p}})$ is
a polynomial function of the coordinates of ${\bm{p}}$, we can choose a base
of the space of $C_{2}^{1}$-motions of $(G,{\bm{p}})$ such that each entry of
the vectors in the base is a polynomial function of the coordinates of
${\bm{p}}$. By the assumption of the lemma, $(G,{{\bm{p}}})$ has a $b$-motion
for some generic ${{\bm{p}}}$, which is spanned by this base. Since this holds
for some generic ${{\bm{p}}}$ and $b$ is a polynomial function, it will hold
for all generic ${\bm{p}}$. The statement of Lemma 5.6 follows for all generic
${\bm{p}}$. We need a slightly more involved argument to verify the statement
for all ${\bm{p}}\in S$. This is given in Appendix A.

Suppose $v_{0}$ is a vertex of type $(\star)$ in a generic framework
$(G,{\bm{p}})$ and $(G,{\bm{p}})$ is not $C_{2}^{1}$-rigid. Then Lemma 5.1
tells us that $(G,{\bm{p}})$ has a non-trivial motion ${\bm{q}}$ with the
property that the value of ${\bm{q}}$ at each vertex of $\hat{N}_{G}(v_{0})$
can be described by three polynomials in the coordinates of
${\bm{p}}(\hat{N}_{G}(v_{0}))$ with coefficients in ${\mathbb{Q}}$. We will
see in Lemma 5.7 below that ${\bm{q}}$ also has the property that the graph on
$N_{G}(v_{0})$ with edge set
$\\{v_{i}v_{j}\,:\,D(v_{i},v_{j})\cdot({\bm{q}}(v_{i})-{\bm{q}}(v_{j}))=0\\}$
is a star. We will concentrate on $b$-motions which share these properties.

Formally, let $(G,{\bm{p}})$ be a framework and $v_{0}$ be a vertex of degree
five in $G$ with $N_{G}(v_{0})=\\{v_{1},v_{2},\ldots,v_{5}\\}$. We say that a
$C_{2}^{1}$-motion ${\bm{q}}$ of $(G,{\bm{p}})$ is bad at $v_{0}$ if
${\bm{q}}$ is a $b$-motion for some
$b:\hat{N}_{G}(v_{0})\to{\mathbb{Q}}[X_{0},Y_{0},X_{1},Y_{1},\ldots,X_{5},Y_{5}]^{3}$
for which

the graph on $N_{G}(v_{0})$ with edge set
$\\{v_{i}v_{j}:D_{i,j}\cdot(b(v_{i})-b(v_{j}))=0\\}$ is a star, (35)

where
$D_{i,j}=((X_{i}-X_{j})^{2},(X_{i}-X_{j})(Y_{i}-Y_{j}),(Y_{i}-Y_{j})^{2})$.
(Here $D_{i,j}\cdot(b(v_{i})-b(v_{j}))=0$ means that polynomial
$D_{i,j}\cdot(b(v_{i})-b(v_{j}))$ is identically zero.)

Our next result verifies that the motion defined in Lemma 5.1 is indeed a bad
motion.

######  Lemma 5.7.

Let $(G,{\bm{p}})$ be a generic framework and $v_{0}$ be a vertex of type
$(\star)$ with $N_{G}(v_{0})=\\{v_{1},\dots,v_{5}\\}$. Suppose that $G$ is not
$C_{2}^{1}$-rigid. Then $(G,{\bm{p}})$ has a bad motion at $v_{0}$.

###### Proof.

Motivated by Lemma 5.1, we define
$b:\hat{N}_{G}(v_{0})\rightarrow{\mathbb{Q}}[X_{0},Y_{0},X_{1},\ldots,Y_{5}]^{3}$
by

$\displaystyle b(v_{0})$
$\displaystyle=\Delta_{1,2,3}\left|\begin{array}[]{c}D_{0,3}\\\ D_{3,4}\\\
D_{3,5}\end{array}\right|\left|\begin{array}[]{c}D_{0,2}\\\ D_{2,4}\\\
D_{2,5}\end{array}\right|D_{0,1}\times D_{0,5},$ (42) $\displaystyle b(v_{1})$
$\displaystyle=0,$ (43) $\displaystyle b(v_{2})$
$\displaystyle=\beta\Delta_{1,3,2}D_{2,4}\times D_{2,5},$ (44) $\displaystyle
b(v_{3})$ $\displaystyle=\alpha\Delta_{1,2,3}D_{3,4}\times D_{3,5},$ (45)
$\displaystyle b(v_{4})$ $\displaystyle=\alpha\Delta_{1,2,4}D_{3,4}\times
D_{4,5}+\beta\Delta_{1,3,4}D_{2,4}\times D_{4,5},$ (46) $\displaystyle
b(v_{5})$ $\displaystyle=0;$ (47)

where $\Delta_{i,j,k}=\left|\begin{array}[]{ccc}X_{i}&Y_{i}&1\\\
X_{j}&Y_{j}&1\\\ X_{k}&Y_{k}&1\end{array}\right|$,
$\alpha=\left|\begin{array}[]{c}D_{0,2}\\\ D_{2,4}\\\
D_{2,5}\end{array}\right|\left|\begin{array}[]{c}D_{0,3}\\\ D_{0,1}\\\
D_{0,5}\end{array}\right|$, $\beta=-\left|\begin{array}[]{c}D_{0,3}\\\
D_{3,4}\\\ D_{3,5}\end{array}\right|\left|\begin{array}[]{c}D_{0,2}\\\
D_{0,1}\\\ D_{0,5}\end{array}\right|$ are regarded as polynomials in
$X_{0},Y_{0},X_{1},\ldots,Y_{5}$. Then, by Lemma 5.1, $(G,{\bm{p}})$ has a
$b$-motion at $v_{0}$.

It remains to show that $b$ satisfies (35) symbolically. This can be done by a
hand computation using the explicit formulae, see Appendix B for the details.
∎

Our next result asserts that no generic framework with one degree of freedom
can have a bad motion.

######  Theorem 5.8.

Let $(G,{\bm{p}})$ be a generic 1-dof framework and $v_{0}$ be a vertex of
degree five. Then $(G,{\bm{p}})$ has no bad motion at $v_{0}$.

We will delay the proof of Theorem 5.8 until Section 6. Instead we show how it
can be used to deduce Theorem 4.6.

Proof of Theorem 4.6. Suppose the theorem is false. Let $G$ be a
counterexample and ${\bm{p}}$ be a generic realisation of $G$. Then Lemma 5.7
implies that $(G,{\bm{p}})$ has a bad motion at $v_{0}$ and this contradicts
Theorem 5.8. (Note that $(G,{\bm{p}})$ is a 1-dof framework since $v_{0}$ is
type $(\star)$.) ∎

###  5.3 Projective transformations

Recall that each point $p=(x,y)\in{\mathbb{R}}^{2}$ can be associated to a
point $p^{\uparrow}=[x,y,1]^{T}$ in 2-dimensional real projective space. A map
$f:{\mathbb{R}}^{2}\to{\mathbb{R}}^{2}$ is a projective transformation if
there exists a $3\times 3$ non-singular matrix $M$ such that, for all
$p\in{\mathbb{R}}^{2}$, $f(p)^{\uparrow}=\lambda_{p}Mp^{\uparrow}$ for some
non-zero $\lambda_{p}\in{\mathbb{R}}$. We say that a framework
$(G,{\bm{p}}^{\prime})$ is a projective image of a framework $(G,{\bm{p}})$ if
there is a projective transformation
$f:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ such that
${\bm{p}}^{\prime}(v_{i})=f({\bm{p}}(v_{i}))$ for all $v_{i}\in V(G)$.
Whiteley [22, Theorem 11.3.2.] showed that $C_{2}^{1}$-rigidity is invariant
under projective transformations. We shall use the following lemma, which
implies that a certain projective transformation preserves the existence of a
bad motion, to simplify our calculations in the proof of Theorem 5.8. Its
statement implicitly uses the fact that, for any two ordered sets $S$ and $T$
of four points in general position in ${\mathbb{R}}^{2}$, there is a unique
projective transformation that maps $S$ onto $T$.

######  Lemma 5.9.

Let $(G,{\bm{p}})$ be a generic framework, $v_{0}$ be a vertex of degree five
with $N_{G}(v_{0})=\\{v_{1},\dots,v_{5}\\}$ and $(G,{\bm{p}}^{\prime})$ be a
projective image of $(G,{\bm{p}})$ such that ${\bm{p}}^{\prime}(v_{1})=(1,0)$,
$\ {\bm{p}}^{\prime}(v_{2})=(0,0)$, ${\bm{p}}^{\prime}(v_{3})=(0,1)$, and
${\bm{p}}^{\prime}(v_{4})=(1,1)$. If $(G,{\bm{p}}^{\prime})$ has a bad motion
at $v_{0}$, then $(G,{\bm{p}})$ has a bad motion at $v_{0}$.

Lemma 5.9 will follow from the fact that the entries in the matrix which
defines the projective transformation given in the lemma are determined by the
coordinates of ${\bm{p}}(v_{i})$ for $1\leq i\leq 4$. However, a rigorous
proof seems to require a precise understanding of how the projective
transformation changes the motion space of the framework. Whiteley’s proof of
projective invariance does not provide this as it uses a self-stress argument.
We develop a new proof technique for the projective invariance of
$C_{2}^{1}$-rigidity in Appendix C, and then use it to derive Lemma 5.9.

##  6 Proof of Theorem 5.8

###  6.1 Locally $k$-dof parts

Let $G=(V,E)$ be a graph. A set $X\subseteq V$ is said to be a locally
$C_{2}^{1}$-rigid part in $G$ if every edge in $K(X)$ is in ${\rm cl}(E(G))$.
The set $X$ is said to be a locally $k$-dof part in $G$ if there is a set $F$
of $k$ edges in $K(V)$ such that $X$ is a locally $C_{2}^{1}$-rigid part in
$G+F$, but no smaller edge set has this property.

Our inductive proof of Theorem 5.8 requires the following more general
inductive hypothesis.

######  Theorem 6.1.

Let $(G,{\bm{p}})$ be a generic framework and $v_{0}$ be a vertex of degree
five such that $\hat{N}_{G}(v_{0})$ is a locally $k$-dof part in $G$ with
$k=1$ or $k=2$. Then $(G,{\bm{p}})$ has no bad motion at $v_{0}$.

We give an outline of the proof of Theorem 6.1 in Section 6.2, and delay the
full proof to Section 6.3.

###  6.2 Outline of the proof of Theorem 6.1

Theorem 6.1 is proved by contradiction. We choose a counterexample
$(G,{\bm{p}})$ with $G=(V,E)$ and $|V|$ as small as possible and, subject to
this condition, $k$ as small as possible. The proof proceeds as follows.

Section 6.3.1.

The first step is to prove that $G$ is a 2-dof graph (Claim 6.6) and $G$ has a
vertex $u_{0}$ of degree five with $u_{0}\notin\hat{N}_{G}(v_{0})$ (Claim
6.9).

Sections 6.3.2 and 6.3.3.

Let $G_{0}=(V_{0},E_{0})=G-u_{0}$. We prove statement (46): ${\rm
cl}(E_{0})\cap K(N_{G}(u_{0}))$ is a star on five vertices. The proof of (63)
proceeds as in that of Lemma 4.1, but to apply a similar argument we need to
prepare several preliminary claims in Section 6.3.2.

Section 6.3.4.

The final goal of the proof is to contradict the minimal choice of
$(G,{\bm{p}})$ by showing that $(G_{0}+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$ is a
2-dof framework with a bad motion at $v_{0}$ for two edges $e_{1},e_{2}\in
K(N_{G}(u_{0}))$. To do this we prove the existence of distinct edges
$f_{1},f_{2}\in K(N_{G}(v_{0}))$ such that $G+f_{1}+f_{2}$ is
$C_{2}^{1}$-rigid and distinct edges $e_{j,1},e_{j,2}\in K(N_{G}(u_{0}))$ for
$j=1,2,3$ such that $(G_{0}+f_{i}+e_{j,1}+e_{j,2},{\bm{p}})$ has a non-trivial
motion ${\bm{q}}_{j}^{i}$ for all $i=1,2$ and $j=1,2,3$ so that
$Z(G_{0}+f_{i},{\bm{p}}|_{V_{0}})=Z_{0}(G_{0}+f_{i},{\bm{p}}|_{V_{0}})\oplus\langle{\bm{q}}_{1}^{i},{\bm{q}}_{2}^{i},{\bm{q}}_{3}^{i}\rangle$.

Section 6.3.5.

Let ${\bm{q}}^{i}$ be a nontrivial motion of $(G+f_{i},{\bm{p}})$ for $i=1,2$.
Since $G+f_{1}+f_{2}$ is $C_{2}^{1}$-rigid, we have
$Z(G,{\bm{p}})=Z_{0}(G,{\bm{p}})\oplus\langle{\bm{q}}^{1},{\bm{q}}^{2}\rangle$.
By
$Z(G_{0}+f_{i},{\bm{p}}|_{V_{0}})=Z_{0}(G_{0}+f_{i},{\bm{p}}|_{V_{0}})\oplus\langle{\bm{q}}_{1}^{i},{\bm{q}}_{2}^{i},{\bm{q}}_{3}^{i}\rangle$,
we may suppose (by subtracting a suitable trivial motion) that, for both
$i=1,2$, ${\bm{q}}^{i}|_{V_{0}}=\sum_{j=1}^{3}\alpha_{j}^{i}{\bm{q}}_{j}^{i}$
for some scalars $\alpha_{j}^{i}$.

Since ${\rm cl}(E_{0})\cap K(N_{G}(u_{0}))$ forms a star on five vertices, we
can use the proof technique of Lemma 5.1 to derive an explicit formula for the
scalars $\alpha^{i}_{j}$.

Section 6.3.6.

The original framework $(G,{\bm{p}})$ has a bad motion ${\bm{q}}_{\rm bad}$ at
$v_{0}$, and its restriction to $V_{0}$ is a motion of
$(G_{0},{\bm{p}}|_{V_{0}})$. Since
$Z(G,{\bm{p}})=Z_{0}(G,{\bm{p}})\oplus\langle{\bm{q}}^{1},{\bm{q}}^{2}\rangle$,
we have

${\bm{q}}_{\rm
bad}|_{\hat{N}(v_{0})}\in\left\langle\sum_{j=1}^{3}\alpha_{j}^{1}\,{\bm{q}}_{j}^{1}|_{\hat{N}(v_{0})},\sum_{j=1}^{3}\alpha_{j}^{2}\,{\bm{q}}_{j}^{2}|_{\hat{N}(v_{0})}\right\rangle.$

We can use the explicit formulae for the scalars $\alpha_{j}^{i}$ derived in
Section 6.3.5 and the facts that the entries of ${\bm{q}}_{\rm
bad}|_{\hat{N}(v_{0})}$ are contained in $\mathbb{Q}({\bm{p}}(V_{0}))$ and
$p(u_{0})$ is generic over $\mathbb{Q}({\bm{p}}(V_{0}))$ to show that

${\bm{q}}_{\rm
bad}|_{\hat{N}(v_{0})}\in\left\langle{\bm{q}}_{j}^{1}|_{\hat{N}(v_{0})},{\bm{q}}_{j}^{2}|_{\hat{N}(v_{0})}\right\rangle$

for some $j\in\\{1,2,3\\}$. Since any linear combination of ${\bm{q}}_{j}^{1}$
and ${\bm{q}}_{j}^{2}$ is a motion of
$(G_{0}+e_{j,1}+e_{j,2},{\bm{p}}|_{V_{0}})$, this implies that
$(G_{0}+e_{j,1}+e_{j,2},{\bm{p}}|_{V_{0}})$ has a bad motion at $v_{0}$. This
contradiction to the minimal choice of $(G,{\bm{p}})$ completes the proof.

###  6.3 Proof of Theorem 6.1

We assume the statement of Theorem 6.1 is false and choose a counterexample
$(G,{\bm{p}})$ with $G=(V,E)$ and $v_{0}\in V$ such that the $G$ is minimal
under the lexicographic ordering given by $(|V|,k,\mbox{dof }G,|E|)$. Then
$(G,{\bm{p}})$ has a bad motion at $v_{0}$, $d_{G}(v_{0})=5$ and
$\hat{N}_{G}(v_{0})$ is a locally $k$-dof part in $G$.

####  6.3.1 Preliminary results on the structure of $G$

The first step of the proof is to show that $G$ is a
${C}_{2}^{1}$-independent, 2-dof graph (statement (49) and Claims 6.2 and 6.6)
and $G$ has a vertex $u_{0}$ of degree five with
$u_{0}\notin\hat{N}_{G}(v_{0})$ (Claim 6.9).

Let $N_{G}(v_{0})=\\{v_{1},\dots,v_{5}\\}$ and denote for simplicity
$K_{v}=K(N_{G}(v_{0}))$. Since $(G,{\bm{p}})$ is a counterexample,
$(G,{\bm{p}})$ has a $b$-motion ${\bm{q}}_{\rm bad}$ for some
$b:\hat{N}_{G}(v_{0})\rightarrow\mathbb{Q}[X_{0},Y_{0},\dots,Y_{5}]$ which
satisfies (35). Relabeling $N_{G}(v_{0})$ if necessary, we may suppose that,
for all $v_{i},v_{j}\in N_{G}(v_{0})$ with $i<j$,

$D(v_{i},v_{j})\cdot({\bm{q}}_{\rm bad}(v_{i})-{\bm{q}}_{\rm bad}(v_{j}))=0$
holds if and only if $j=5$. (48)

By (48), $v_{i}v_{j}\notin{\rm cl}(E)$ for all $1\leq i<j\leq 4$. If
$v_{i}v_{5}\notin{\rm cl}(E)$ for some $1\leq i\leq 4$, then again by (48),
$(G+v_{i}v_{5},{\bm{p}})$ would be a $(k-1)$-dof framework having the bad
motion ${\bm{q}}_{\rm bad}$, which would contradict either the fact that
$(G+v_{i}v_{5},{\bm{p}})$ is $C^{1}_{2}$-rigid (when $k=1$) or the minimality
of $k$ (when $k=2$). Hence, for all $v_{i},v_{j}\in N_{G}(v_{0})$, we have
$v_{i}v_{j}\in{\rm cl}(E)$ if and only if $j=5$. Then
$\operatorname{cl}(E)\cap K_{v}$ induces a star on five vertices so is
${C}_{2}^{1}$-independent. This implies that we may choose a base $E^{\prime}$
of $\operatorname{cl}(E)$ in ${\cal C}_{2}^{1}$ with $\operatorname{cl}(E)\cap
K_{v}\subseteq E^{\prime}$ and $N_{E}(v_{0})=N_{E^{\prime}}(v_{0})$. Let
$G^{\prime}$ be the subgraph of $K(V)$ induced by $E^{\prime}$. Then
$(G,{\bm{p}})$ and $(G^{\prime},{\bm{p}})$ have the same space of motions. The
minimality of $|E|$ now implies that $|E|=|E^{\prime}|$ and $G$ is
${C}_{2}^{1}$-independent. Replacing $G$ by $G^{\prime}$ if necessary, we may
assume that

$G$ is ${C}_{2}^{1}$-independent and $E\cap K_{v}={\rm cl}(E)\cap K_{v}$ is a
star on five vertices centred on $v_{5}$. (49)

######  Claim 6.2.

$G$ is a $k$-dof graph.

###### Proof.

Suppose that $G$ has $k^{\prime}$ degrees of freedom. We show that there
exists a set of $(k^{\prime}-k)$ edges $D$ of $K(V-v_{0})$ such that $G+D$ is
a $k$-dof graph, $X:=\hat{N}_{G}(v_{0})$ is a locally $k$-dof part in $G+D$
and, for any generic framework $(G,{\bm{p}})$ and any motion ${\bm{q}}$ of
$(G,{\bm{p}})$, $(G+D,{\bm{p}})$ has a motion ${\bm{q}}^{\prime}$ satisfying
${\bm{q}}^{\prime}(v)={\bm{q}}(v)$ for all $v\in X$.

Let $F$ be a set of $k$ edges in $K(V)$ such that $X$ is a locally
$C_{2}^{1}$-rigid part in $G+F$, and $D$ be a minimal set of edges in
$K(V-v_{0})$ such that $G+F+D$ is $C^{1}_{2}$-rigid. (Note that $D$ exists
since $d_{G}(v_{0})=5$.) For each $e\in F\cup D$, $G+F+D-e$ is a 1-dof graph
and we can choose a non-trivial $C^{1}_{2}$-motion ${\bm{q}}_{e}$ of
$(G+F+D-e,{\bm{p}})$. Then $B_{1}:=\\{{\bm{q}}_{i}^{*}\,:\,1\leq i\leq
6\\}\cup\\{{\bm{q}}_{e}\,:\,e\in F\cup D\\}$ is a base for $Z(G,{\bm{p}})$ and
$B_{2}:=\\{{\bm{q}}_{i}^{*}\,:\,1\leq i\leq 6\\}\cup\\{{\bm{q}}_{e}\,:\,e\in
F\\}$ is a base for $Z(G+D,{\bm{p}})$, where $\\{q_{i}^{*}:1\leq i\leq 6\\}$
is the basis for $Z_{0}(G,p)$ given in Section 2.2. The facts that the motions
in $B_{1}$ are linearly independent and that, for each $e\in F$, we have
$D(u,v)\cdot({\bm{q}}_{e}(u)-{\bm{q}}_{e}(v))\neq 0$ for some $u,v\in X$ now
imply that we must add at least $k$ edges to $G+D$ to make $X$ locally
$C_{2}^{1}$-rigid. Hence $X$ is a locally $k$-dof part in $G+D$.

Let ${\bm{q}}$ be a motion of $(G,{\bm{p}})$. Since $B_{1}$ is a base for
$Z(G,{\bm{p}})$, we have
${\bm{q}}=\sum_{i=1}^{6}\lambda_{i}{\bm{q}}_{i}^{*}+\sum_{e\in F\cup
D}\mu_{e}{\bm{q}}_{e}$ for some $\lambda_{i},\mu_{e}\in{\mathbb{R}}$. Since
$X$ is a locally $C_{2}^{1}$-rigid part of $G+F$, ${\bm{q}}_{e}|_{X}$ is a
trivial motion of $(K(X),{\bm{p}}|_{X})$ for all $e\in D$. Hence
${\bm{q}}_{e}|_{X}={\bm{q}}_{e}^{*}|_{X}$ for some trivial motion
${\bm{q}}_{e}^{*}$ of $(G,{\bm{p}})$. Let
${\bm{q}}^{\prime}=\sum_{i=1}^{6}\lambda_{i}{\bm{q}}_{i}^{*}+\sum_{e\in
F}\mu_{e}{\bm{q}}_{e}+\sum_{e\in D}\mu_{e}{\bm{q}}_{e}^{*}$. Then
${\bm{q}}^{\prime}\in Z(G+D,{\bm{p}})$. Since
${\bm{q}}_{e}|_{X}={\bm{q}}_{e}^{*}|_{X}$ for $e\in D$, we also have
${\bm{q}}^{\prime}|_{X}={\bm{q}}|_{X}$.

Hence $(G+D,{\bm{p}})$ is a counterexample. The minimality of dof $G$ now
implies that $k^{\prime}=k$ and $D=\emptyset$. Hence $G$ is a $k$-dof graph. ∎

As $G$ is a $k$-dof graph for some $1\leq k\leq 2$, (49) implies that $|V|\geq
7$.

######  Claim 6.3.

$G$ has a vertex $u_{0}$ of degree at most five with
$u_{0}\notin\hat{N}_{G}(v_{0})$.

###### Proof.

Put $G-\hat{N}_{G}(v_{0})=G^{\prime}=(V^{\prime},E^{\prime})$ and let $F$ be
the set of edges of $G$ from $\hat{N}_{G}(v_{0})$ to $V^{\prime}$. Since
$|V|\geq 7$, we have $|V^{\prime}|\geq 1$. By (49) we have

$9+|F|+|E^{\prime}|=|E|=3|V|-6-k=3(|V^{\prime}|+6)-6-k.$ (50)

Suppose every vertex in $V^{\prime}$ has degree at least six in $G$. Then

$\sum_{v^{\prime}\in V^{\prime}}d_{G}(v^{\prime})=|F|+2|E^{\prime}|\geq
6|V^{\prime}|.$ (51)

We can now use (50) and (51) to deduce that $|E^{\prime}|\geq
3|V^{\prime}|-3+k\geq 3|V^{\prime}|-2$. This contradicts the fact that $G$ is
$C_{2}^{1}$-independent. ∎

Let $u_{0}\in V\setminus\hat{N}_{G}(v_{0})$ be a vertex of degree at most five
in $G$, $K_{u}=K(N_{G}(u_{0}))$ and put $G-u_{0}=G_{0}=(V_{0},E_{0})$. Let
${\cal C}_{n-1}$ be the generic $C_{2}^{1}$-cofactor matroid on $K(V_{0})$ and
let ${\cal C}_{n-1}/{\rm cl}(E_{0})$ be the matroid obtained from ${\cal
C}_{n-1}$ by contracting ${\rm cl}(E_{0})$.

######  Claim 6.4.

$F_{v}:=\\{v_{1}v_{2},v_{1}v_{3},v_{1}v_{4}\\}$ is a base of
$K_{v}\setminus{\rm cl}(E_{0})$ in ${\cal C}_{n-1}/{\rm cl}(E_{0})$ (and hence
$K_{v}\setminus{\rm cl}(E_{0})$ has rank three in ${\cal C}_{n-1}/{\rm
cl}(E_{0})$).

###### Proof.

By (49) the subgraph of $G+F_{v}$ induced by $\hat{N}_{G}(v_{0})$ is
$C_{2}^{1}$-rigid. Hence $F_{v}$ spans $K_{v}\setminus{\rm cl}(E_{0})$ in
${\cal C}_{n-1}/{\rm cl}(E_{0})$. Choose a base $F^{\prime}$ of $F_{v}$ in
${\cal C}_{n-1}/{\rm cl}(E_{0})$. Since the closure of $F^{\prime}$ contains
$F_{v}$, ${\rm cl}(E_{0}\cup F^{\prime})$ contains a $C^{1}_{2}$-rigid
subgraph on $\hat{N}_{G}(v_{0})$. Hence $\hat{N}_{G}(v_{0})$ is a locally
$t$-dof part in $G_{0}$ with $t=|F^{\prime}|$. Since ${\bm{q}}_{\rm
bad}|_{V_{0}}$ is a bad motion of $(G_{0},{\bm{p}}|_{V_{0}})$ at $v_{0}$ and
$G_{0}$ is not a counterexample by the minimality of $|V|$, we must have
$t=|F^{\prime}|=3$ and $F^{\prime}=F_{v}$. ∎

######  Claim 6.5.

$d_{G}(u_{0})\in\\{4,5\\}$.

###### Proof.

If $d_{G}(u_{0})\leq 3$, then $G_{0}$ would be a $t$-dof graph for some $t\leq
2$. This would contradict Claim 6.4. ∎

######  Claim 6.6.

$k=2$.

###### Proof.

Suppose for a contradiction that $k=1$. If $d_{G}(u_{0})=4$ then $G_{0}$ would
be a $t$-dof graph for some $t\leq 2$ and this would contradict Claim 6.4.
Hence we may suppose $d_{G}(u_{0})=5$. Let
$N_{G}(u_{0})=\\{u_{1},u_{2},\ldots,u_{5}\\}$. We will obtain a contradiction
by showing that $(G_{0}+u_{i}u_{j},{\bm{p}}|_{V_{0}})$ has a bad motion at
$v_{0}$ for some $1\leq i<j\leq 5$.

Since $G$ is a 1-dof graph, $G_{0}$ is a 3-dof graph and hence, by Claim 6.4,
$G_{0}+F_{v}$ is minimally $C_{2}^{1}$-rigid. As
$G+F_{v}-u_{0}u_{4}-u_{0}u_{5}$ is obtained from $G_{0}+F_{v}$ by a
0-extension, Lemma 3.1 now implies that $G+F_{v}-u_{0}u_{4}-u_{0}u_{5}$ is
minimally $C_{2}^{1}$-rigid. Since $G$ is $C_{2}^{1}$-independent,
$G+F-u_{0}u_{5}$ is minimally $C_{2}^{1}$-rigid for some $F\subset F_{v}$ with
$|F|=2$. We may now deduce that $G_{0}+F+u_{i}u_{j}$ is minimally
$C_{2}^{1}$-rigid for some $1\leq i<j\leq 4$, and hence that
$G_{0}+u_{i}u_{j}$ is a 2-dof graph. It remains to show that there is a bad
motion for $(G_{0}+u_{i}u_{j},{\bm{p}}|_{V_{0}})$ at $v_{0}$.

Let $G^{\prime}=G-u_{0}u_{5}$. Observe that $G^{\prime}$ is obtained from
$G_{0}+u_{i}u_{j}$ by a 1-extension. We shall consider the following non-
generic realisation ${\bm{p}}^{\prime}$ of $G^{\prime}$, which was used in the
proof of [22, Theorem 10.2.1] to show that 1-extension preserves independence.
For $w\in V$, let

${\bm{p}}^{\prime}(w)=\begin{cases}{\bm{p}}(w)&(\text{if }w\in
V\setminus\\{u_{0}\\})\\\ \text{the mid-point of the line segment joining
${\bm{p}}(u_{i})$ and ${\bm{p}}(u_{j})$}&(\text{if }w=u_{0}).\end{cases}$

See Figure 5.

(a)

(b)

Figure 5: (a) $(G^{\prime},{\bm{p}}^{\prime})$ and (b)
$(G_{0}+u_{i}u_{j},{\bm{p}}_{|V_{0}})$.

We now use Lemma 5.6 to show that $(G^{\prime},{\bm{p}}^{\prime})$ has a bad
motion at $v_{0}$. Let

$S=\left\\{\bar{\bm{p}}:\text{$(G^{\prime}+F,\bar{\bm{p}})$ is minimally
$C_{2}^{1}$-rigid and $\bar{\bm{p}}$ is non-degenerate on
$\hat{N}_{G^{\prime}}(v_{0})$}\right\\}.$

We may use the minimal $C_{2}^{1}$-rigidity of
$(G_{0}+F+u_{i}u_{j},{\bm{p}}|_{V_{0}})$, and the fact that
$\\{u_{0},u_{i},u_{j}\\}$ is collinear in
$(G^{\prime}+F+u_{i}u_{j},{\bm{p}}^{\prime})$ to deduce that
$(G^{\prime}+F,{\bm{p}}^{\prime})$ is minimally $C_{2}^{1}$-rigid, see the
proof of [22, Theorem 10.2.1] for more details. Since ${\bm{p}}$ is generic,
${\bm{p}}^{\prime}$ is non-degenerate on $\hat{N}_{G^{\prime}}(v_{0})$ and
hence ${\bm{p}}^{\prime}\in S$. Since ${\bm{q}}_{\rm bad}$ is a bad motion of
$(G^{\prime},{\bm{p}})$ at $v_{0}$, Lemma 5.6 now implies that
$(G^{\prime},{\bm{p}}^{\prime})$ has a bad motion ${\bm{q}}_{\rm
bad}^{\prime}$ at $v_{0}$. The definition of ${\bm{p}}^{\prime}$ implies that
${\bm{q}}_{\rm bad}^{\prime}|_{V_{0}}$ is a motion of
$(G_{0}+u_{i}u_{j},{\bm{p}}|_{V_{0}})$. Since
$(G_{0}+u_{i}u_{j},{\bm{p}}|_{V_{0}})$ is a generic 2-dof framework,
${\bm{q}}_{\rm bad}^{\prime}|_{V_{0}}$ is bad at $v_{0}$ and this contradicts
the minimality of $G$. ∎

Recall that $F_{v}=\\{v_{1}v_{2},v_{1}v_{3},v_{1}v_{4}\\}$. We will denote the
set of all pairs of edges in $F_{v}$ by ${F_{v}\choose 2}$. We say that
$F\in{F_{v}\choose 2}$ is good if $G+F$ is $C_{2}^{1}$-independent (and hence
minimally $C_{2}^{1}$-rigid by $k=2$). We say that an edge $f\in F_{v}$ is
very good if $\\{f,f^{\prime}\\}$ is good for any $f^{\prime}\in
F_{v}\setminus\\{f\\}$.

######  Claim 6.7.

There is at least one very good edge in $F_{v}$. (Equivalently, at most one
pair in ${F_{v}\choose 2}$ is not good).

###### Proof.

Let $F_{v}=\\{f_{1},f_{2},f_{3}\\}$, and suppose that $\\{f_{1},f_{2}\\}$ and
$\\{f_{1},f_{3}\\}$ are not good. By (49), $f_{1}\notin{\rm cl}(E)$. Hence
$G+f_{1}$ is $C_{2}^{1}$-independent and $f_{2},f_{3}\in{\rm cl}(E+f_{1})$.
This in turn implies that $K_{v}\subseteq{\rm cl}(E+f_{1})$ and hence
$\hat{N}_{G}(v_{0})$ is a locally 1-dof part in $G$. This is a contradiction
as $\hat{N}_{G}(v_{0})$ is a locally $k$-dof part with $k=2$ by Claim 6.6. ∎

######  Claim 6.8.

Let $F\in{F_{v}\choose 2}$ be a good pair. Then ${\rm cl}(E_{0}\cup F)\cap
K_{u}$ does not contain a copy of $K_{4}$.

###### Proof.

Suppose that ${\rm cl}(E_{0}\cup F)\cap K_{u}$ contains a copy of $K_{4}$, say
on $\\{u_{1},\dots,u_{4}\\}\subseteq N_{G}(u_{0})$. Then
$u_{0}u_{4}\in\operatorname{cl}((E_{0}\cup
F)+u_{0}u_{1}+u_{0}u_{2}+u_{0}u_{3})$. This in turn implies that $E\cup F$ is
dependent and contradicts the hypothesis that $F$ is good. ∎

######  Claim 6.9.

$d_{G}(u_{0})=5$.

###### Proof.

Assume this is false. Then by Claim 6.5, $d_{G}(u_{0})=4$. Choose a good pair
$F\in{F_{v}\choose 2}$. By Claim 6.8, there is an edge $e=u_{i}u_{j}\in K_{u}$
such that $G_{0}+F+u_{i}u_{j}$ is $C_{2}^{1}$-independent. Since
$d_{G}(u_{0})=4$, it is minimally $C_{2}^{1}$-rigid. We can now proceed as in
the last paragraph of the proof of Claim 6.6 (with $G^{\prime}$ replaced by
$G$) to show that $(G_{0}+u_{i}u_{j},{\bm{p}}|_{V_{0}})$ has a bad motion at
$v_{0}$ and hence contradict the minimality of $|V|$. ∎

####  6.3.2 Preliminary results on $\operatorname{cl}(E_{0})\cap K_{u}$

Our next goal is to show that ${\rm cl}(E_{0})\cap K_{u}$ is a star on five
vertices (statement (63) in the next section). In this section we verify some
preliminary claims. Let $N_{G}(u_{0})=\\{u_{1},u_{2},\ldots,u_{5}\\}$.

######  Claim 6.10.

$G_{0}+F+e_{1}+e_{2}$ is $C_{2}^{1}$-dependent for all $F\in{F_{v}\choose 2}$
and all pairs of non-adjacent edges $e_{1},e_{2}\in K_{u}\setminus E_{0}$.

###### Proof.

Suppose that $G_{0}+F+e_{1}+e_{2}$ is $C_{2}^{1}$-independent (and hence
minimally $C_{2}^{1}$-rigid) for $e_{1}=u_{1}u_{2}$ and $e_{2}=u_{3}u_{4}$. We
will contradict the minimality of $G$ by showing that
$(G_{0}+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$ has a bad motion at $v_{0}$.

Observe that $G+F$ is obtained from $G_{0}+F+e_{1}+e_{2}$ by an X-replacement.
We shall consider the following non-generic realisation ${\bm{p}}^{\prime}$ of
$G$, which was used in the proof of [22, Theorem 10.3.1] to show that
X-replacement preserves $C_{2}^{1}$-independence. For $w\in V$, let
${\bm{p}}^{\prime}(w)={\bm{p}}(w)$ for $w\in V_{0}$ and
${\bm{p}}^{\prime}(u_{0})$ be the point of intersection of the line through
${\bm{p}}(u_{1})$ and ${\bm{p}}(u_{2})$, and the line through
${\bm{p}}(u_{3})$ and ${\bm{p}}(u_{4})$. We first use Lemma 5.6 to show that
$(G,{\bm{p}}^{\prime})$ has a bad motion at $v_{0}$. To do this, let

$S=\left\\{\bar{\bm{p}}:\text{$(G+F,\bar{\bm{p}})$ is minimally
$C_{2}^{1}$-rigid and $\bar{\bm{p}}$ is non-degenerate on
$\hat{N}_{G}(v_{0})$}\right\\}.$

We may use the minimal $C_{2}^{1}$-rigidity of
$(G_{0}+F+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$, and the fact the vertex sets
$\\{u_{0},u_{1},u_{2}\\}$ and $\\{u_{0},u_{3},u_{4}\\}$ are collinear in
$(G+F+e_{1}+e_{2},{\bm{p}}^{\prime})$ to deduce that $(G+F,{\bm{p}}^{\prime})$
is minimally $C_{2}^{1}$-rigid, see the proof of [22, Theorem 10.3.1] for more
details. Since ${\bm{p}}$ is generic, ${\bm{p}}^{\prime}$ is non-degenerate on
$\hat{N}_{G}(v_{0})$ and hence ${\bm{p}}^{\prime}\in S$. Since $(G,{\bm{p}})$
has a bad motion at $v_{0}$, Lemma 5.6 now implies that
$(G,{\bm{p}}^{\prime})$ has a bad motion ${\bm{q}}_{\rm bad}^{\prime}$ at
$v_{0}$. The definition of ${\bm{p}}^{\prime}$ implies that ${\bm{q}}_{\rm
bad}^{\prime}|_{V_{0}}$ is a motion of
$(G_{0}+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$. Since
$(G_{0}+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$ is a generic 2-dof framework,
${\bm{q}}_{\rm bad}^{\prime}|_{V_{0}}$ is bad at $v_{0}$ and this contradicts
the minimality of $G$. ∎

Claim 6.10 implies the following.

######  Claim 6.11.

Let $F\in{F_{v}\choose 2}$ and let $e=u_{i}u_{j}\in K_{u}\setminus E_{0}$ such
that $G_{0}+F+e$ is $C_{2}^{1}$-independent. Then ${\rm cl}((E_{0}\cup F)+e)$
contains a triangle on $N_{G}(u_{0})\setminus\\{u_{i},u_{j}\\}$.

###### Proof.

If not, then we can choose an edge $e^{\prime}$ on
$N_{G}(u_{0})\setminus\\{u_{i},u_{j}\\}$ such that $G_{0}+F+e+e^{\prime}$ is
$C_{2}^{1}$-independent. This contradicts Claim 6.10. ∎

######  Claim 6.12.

$G_{0}+F+e_{1}+e_{2}$ is $C_{2}^{1}$-dependent for all $F\in{F_{v}\choose 2}$
and all pairs of adjacent edges $e_{1},e_{2}\in K_{u}\setminus E_{0}$ whose
common end-vertex has degree two in ${\rm cl}(E_{0})\cap K_{u}$.

###### Proof.

Suppose that $G_{0}+F+e_{1}+e_{2}$ is $C^{1}_{2}$-independent (and hence
minimally $C_{2}^{1}$-rigid). Our aim is to contradict the minimality of $G$
by showing that $(G_{0}+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$ has a bad motion at
$v_{0}$.

Let $u_{1}$ be the common endvertex of $e_{1}$ and $e_{2}$. Since $u_{1}$ has
degree two in $\operatorname{cl}(E_{0})\cap K_{u}$ we may choose a base
$E_{0}^{\prime}$ of $\operatorname{cl}(E_{0})$ such that $u_{1}$ has degree
two in $E_{0}^{\prime}\cap K_{u}$ and $v_{0}$ is incident with the same set of
edges in $E_{0}$ and $E_{0}^{\prime}$. Let $G_{0}^{\prime}$ be the graph
induced by $E_{0}^{\prime}$ and $G^{\prime}$ be the graph obtained from
$G_{0}^{\prime}$ by adding $u$ and the edges of $G$ incident to $u$. Then
$G_{0}^{\prime}+F+e_{1}+e_{2}$ is $C^{1}_{2}$-independent and hence
$G^{\prime}+F$ is $C^{1}_{2}$-independent by Lemma 3.2. In addition, the fact
that $\operatorname{cl}(E_{0})=\operatorname{cl}(E_{0}^{\prime})$ implies that
$(G,p)$ and $(G^{\prime},p)$ will have the same space of motions. Relabelling
$G^{\prime}$ by $G$, we may assume that $u_{1}$ has degree two in $E_{0}\cap
K_{u}$ and $G+F$ is obtained from $G_{0}+F+e_{1}+e_{2}$ by a vertex splitting.

Consider the realisation ${\bm{p}}_{0}$ of $G$ defined by
${\bm{p}}_{0}(w)={\bm{p}}(w)$ for $w\in V_{0}$ and
${\bm{p}}_{0}(u_{0})={\bm{p}}(u_{1})$. Let ${C}^{*}(G+F,{\bm{p}}_{0})$ be
obtained from the cofactor matrix ${C}(G+F,{\bm{p}}_{0})$ by replacing the
zero-row indexed by the edge $u_{0}u_{1}$ with a row of the form

$\hbox{}\vbox{\kern 0.86108pt\hbox{$\kern 0.0pt\kern
2.5pt\kern-5.0pt\left[\kern
0.0pt\kern-2.5pt\kern-5.55557pt\vbox{\kern-0.86108pt\vbox{\vbox{
\halign{\kern\arraycolsep\hfil\@arstrut$\kbcolstyle#$\hfil\kern\arraycolsep&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep&&
\kern\arraycolsep\hfil$\@kbrowstyle#$\ifkbalignright\relax\else\hfil\fi\kern\arraycolsep\cr
5.0pt\hfil\@arstrut$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle
u_{0}$\hfil\kern 5.0pt&5.0pt\hfil$\scriptstyle$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle u_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle\\\e=u_{0}u_{1}$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\dots 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle D({\bm{p}}(u_{0}),{\bm{p}}(u_{1}))$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\dots 0$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle-D({\bm{p}}(u_{0}),{\bm{p}}(u_{1}))$\hfil\kern
5.0pt&5.0pt\hfil$\scriptstyle 0\dots 0$\hfil\kern 5.0pt\crcr}}}}\right]$}}.$

The argument used to show that vertex splitting preserves
$C^{1}_{2}$-independence in [22, Theorem 10.2.7] implies that
${C}^{*}(G+F,{\bm{p}}_{0})$ is row independent. If ${C}^{*}(G+F,{\bm{p}}_{0})$
were the $C^{1}_{2}$-cofactor matrix of $(G+F,{\bm{p}}_{0})$ then we could
find a bad motion for $(G_{0}+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$ by applying
Lemma 5.6 to $(G+F,{\bm{p}}_{0})$ as in the last paragraph of Claim 6.10, and
this would contradict the minimality of $G$. Since ${C}^{*}(G+F,{\bm{p}}_{0})$
is not a $C^{1}_{2}$-cofactor matrix we instead apply the proof technique of
Lemma 5.6 directly to ${C}^{*}(G+F,{\bm{p}}_{0})$ to show that

$z|_{V_{0}}$ is a bad motion of $(G_{0}+e_{1}+e_{2},{\bm{p}}|_{V_{0}})$ for
some $z\in\ker{C}^{*}(G,{\bm{p}}_{0})$ (52)

and obtain the same contradiction. We give the proof of (52) immediately after
the proof of Lemma 5.6 in Appendix A. ∎

####  6.3.3 The structure of ${\rm cl}(E_{0})\cap K_{u}$

We show that ${\rm cl}(E_{0})\cap K_{u}$ is a star on $N_{G}(u_{0})$. The
proof proceeds as in that of Lemma 4.1.

######  Claim 6.13.

For every good pair $F\in{F_{v}\choose 2}$ and every $e\in K_{u}$ such that
$(E_{0}\cup F)+e$ is independent, ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$ does
not contain a $C_{2}^{1}$-rigid subgraph spanning $N_{G}(u_{0})$.

###### Proof.

Suppose ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$ contains a $C_{2}^{1}$-rigid
subgraph spanning $N_{G}(u_{0})$. Then $K_{u}\subseteq{\rm cl}((E_{0}\cup
F)+e)$ and hence $u_{0}u_{4},u_{0}u_{5}\in\operatorname{cl}((E_{0}\cup
F)+e+u_{0}u_{1}+u_{0}u_{2}+u_{0}u_{3})$. Since $G$ is $C_{2}^{1}$-independent,
we can use two base exchanges to show that $\operatorname{cl}((E_{0}\cup
F)+e+u_{0}u_{1}+u_{0}u_{2}+u_{0}u_{3})=\operatorname{cl}(E+e^{\prime})$ for
some $e^{\prime}\in F+e$. Then $F\subseteq\operatorname{cl}(E+e^{\prime})$.
This contradicts the hypothesis that $F$ is good. ∎

For $F\subseteq K(V_{0})\setminus\operatorname{cl}(E_{0})$, we use $[F]$ to
denote the closure of $F$ in ${\cal C}_{n-1}/{\rm cl}(E_{0})$. Thus an edge
$e\in K(V_{0})\setminus{\rm cl}(E_{0})$ belongs to $[F]$ if and only if we
have $e\in C\subseteq(E_{0}\cup F)+e$ for some circuit $C$ of ${\cal
C}_{n-1}$. If $F$ is a singleton $\\{f\\}$, then we denote $[\\{f\\}]$ by
$[f]$.

We say that a set $F\subset F_{v}$ is influential if $[F]\cap
K_{u}\neq\emptyset$. A set $F+e$ with $F\in{F_{v}\choose 2}$ and $e\in
K_{u}\setminus{\rm cl}(E_{0})$ is said to be a stabilizer if $\hat{N}(v_{0})$
is a locally $C_{2}^{1}$-rigid part of $G_{0}+F+e$. By Claim 6.4, $F+e$ is a
stabilizer if and only if ${\rm cl}((E_{0}\cup F)+e)={\rm cl}(E_{0}\cup
F_{v})$. This fact will be used frequently.

######  Claim 6.14.

Let $F\in{F_{v}\choose 2}$ be a good pair and $e\in K_{u}\setminus{\rm
cl}(E_{0})$ such that $(E_{0}\cup F)+e$ is independent. Suppose that either
$F$ is not influential or $F+e$ is a stabilizer. Then ${\rm cl}((E_{0}\cup
F)+e)\cap K_{u}$ contains no copy of $K_{4}$.

###### Proof.

Without loss of generality, let $e=u_{1}u_{2}$.

Suppose that ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$ contains a copy of $K_{4}$.
If ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$ contains two distinct copies of
$K_{4}$, then their union would be a $C^{1}_{2}$-rigid subgraph of $K_{u}$.
This would contradict Claim 6.13. Hence ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$
contains exactly one copy of $K_{4}$. We consider two cases depending on the
position of the copy of $K_{4}$.

_Case 1:_ The copy of $K_{4}$ in ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$
contains $e=u_{1}u_{2}$. By symmetry we may assume that this is a $K_{4}$ on
$\\{u_{1},u_{2},u_{3},u_{4}\\}$. By Claim 6.11, ${\rm cl}((E_{0}\cup F)+e)\cap
K_{u}$ also contains $\\{u_{3}u_{5},u_{4}u_{5}\\}$. Hence, by Claim 6.13,

$u_{1}u_{5},u_{2}u_{5}\notin{\rm cl}((E_{0}\cup F)+e)\cap K_{u}.$

We next show that:

$u_{1}u_{3},u_{1}u_{4}\in{\rm cl}(E_{0}\cup F).$ (53)

To see this, suppose $u_{1}u_{3}\notin{\rm cl}(E_{0}\cup F)$. Since
$u_{1}u_{3}\in{\rm cl}((E_{0}\cup F)+e)$, we have that $(E_{0}\cup
F)+u_{1}u_{3}$ is independent and $u_{2}u_{5}\not\in{\rm cl}((E_{0}\cup
F)+e)={\rm cl}((E_{0}\cup F)+u_{1}u_{3})$. Hence $(E_{0}\cup
F)+u_{1}u_{3}+u_{2}u_{5}$ is independent. This contradicts Claim 6.10 so
$u_{1}u_{3}\in{\rm cl}(E_{0}\cup F)$. The same argument for $u_{1}u_{4}$ gives
(53).

Since $(E_{0}\cup F)+e+u_{1}u_{5}$ is independent, Claim 6.12 implies that
$\\{u_{1}u_{3},u_{1}u_{4}\\}\not\subseteq{\rm cl}(E_{0})$. By symmetry, we may
suppose that $u_{1}u_{3}\notin{\rm cl}(E_{0})$, i.e., $u_{1}u_{3}\in{\rm
cl}((E_{0}\cup F))\setminus{\rm cl}(E_{0})=[F]$. This implies that $F$ is
influential, and hence (by an hypothesis of the claim) $F+e$ is a stabilizer.
Thus, for the unique edge $f_{e}\in F_{v}\setminus F$, we have ${\rm
cl}((E_{0}\cup F)+e)={\rm cl}((E_{0}\cup F)+f_{e})$. Since $u_{1}u_{3}\in[F]$,
we also have $u_{2}u_{5}\not\in{\rm cl}((E_{0}\cup F)+e)={\rm cl}((E_{0}\cup
F)+f_{e})={\rm cl}(E_{0}+f+u_{1}u_{3}+f_{e})$ for some edge $f\in F$. Then
$(E_{0}\cup\\{f,f_{e}\\})+u_{1}u_{3}+u_{2}u_{5}$ is independent. This
contradicts Claim 6.10.

_Case 2:_ ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$ contains a copy of $K_{4}$
which avoids $e=u_{1}u_{2}$. By symmetry we may assume that this is a $K_{4}$
on $\\{u_{1},u_{3},u_{4},u_{5}\\}$. Since there is no other copy of $K_{4}$ in
${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$, we may also assume

$u_{2}u_{3},u_{2}u_{4}\notin{\rm cl}((E_{0}\cup F)+e).$

We proceed in a similar way to Case 1. We first show:

$\\{u_{1}u_{3},u_{1}u_{4},u_{1}u_{5},u_{3}u_{5},u_{4}u_{5}\\}\subseteq{\rm
cl}(E_{0}\cup F).$ (54)

To see this, suppose $u_{1}u_{3}\notin{\rm cl}(E_{0}\cup F)$. Since
$u_{1}u_{3}\in{\rm cl}((E_{0}\cup F)+e)$, $(E_{0}\cup F)+u_{1}u_{3}$ is
independent and $u_{2}u_{4}\notin{\rm cl}((E_{0}\cup F)+e)={\rm cl}((E_{0}\cup
F)+u_{1}u_{3})$. Hence $(E_{0}\cup F)+u_{1}u_{3}+u_{2}u_{4}$ is independent.
This contradicts Claim 6.10. The same proof can be applied to the other edges
to give (54).

We next show that:

$\\{u_{1}u_{3},u_{1}u_{4},u_{1}u_{5},u_{3}u_{5},u_{4}u_{5}\\}\subseteq{\rm
cl}(E_{0}).$ (55)

To see this, suppose $u_{1}u_{3}\notin{\rm cl}(E_{0})$. Then
$u_{1}u_{3}\in{\rm cl}((E_{0}\cup F))\setminus{\rm cl}(E_{0})=[F]$. This
implies that $F$ is influential, and hence (by an hypothesis of the claim)
$F+e$ is a stabilizer. Thus, for the unique edge $f_{e}\in F_{v}\setminus F$,
${\rm cl}((E_{0}\cup F)+e)={\rm cl}((E_{0}\cup F)+f_{e})$ holds, and we have
$u_{2}u_{4}\not\in{\rm cl}((E_{0}\cup F)+e)={\rm cl}((E_{0}\cup F)+f_{e})={\rm
cl}(E_{0}+f+u_{1}u_{3}+f_{e})$ for some edge $f\in F$. Hence
$(E_{0}\cup\\{f,f_{e}\\})+u_{1}u_{3}+u_{2}u_{4}$ is independent. This
contradicts Claim 6.10. The same argument can be applied to the other edges to
give (55).

Suppose that $u_{3}u_{4}\notin{\rm cl}(E_{0}\cup F)$. As $u_{3}u_{4}\in{\rm
cl}((E_{0}\cup F)+e)$, $(E_{0}\cup F)+u_{3}u_{4}$ is independent and
$u_{2}u_{4}\not\in{\rm cl}((E_{0}\cup F)+e)={\rm cl}((E_{0}\cup
F)+u_{3}u_{4})$. Hence $(E_{0}\cup F)+u_{3}u_{4}+u_{2}u_{4}$ is independent.
Since $u_{4}$ has degree two in ${\rm cl}(E_{0})\cap K_{u}$ by (55), this
contradicts Claim 6.12. Hence $u_{3}u_{4}\in{\rm cl}(E_{0}\cup F)$. This and
(54) imply that ${\rm cl}(E_{0}\cup F)$ contains a copy of $K_{4}$ on
$\\{u_{1},u_{3},u_{4},u_{5}\\}$, contradicting Claim 6.8. ∎

######  Claim 6.15.

Let $F\in{F_{v}\choose 2}$ be a good pair and $e=u_{i}u_{j}\in K_{u}$ be such
that $(E_{0}\cup F)+e$ is independent. Suppose that either $F$ is not
influential or $F+e$ is a stabilizer. Then ${\rm cl}(E_{0})$ contains at least
two edges of the triangle on $N_{G}(u_{0})\setminus\\{u_{i},u_{j}\\}$.

###### Proof.

Without loss of generality suppose $e=u_{1}u_{2}$. By Claim 6.11, ${\rm
cl}(E_{0}+F+e)$ contains a triangle on $\\{u_{3},u_{4},u_{5}\\}$.

We first consider the complete graph on $\\{u_{1},u_{2},u_{3},u_{4}\\}$. By
Claim 6.14 we may assume without loss of generality that ${\rm cl}((E_{0}\cup
F)+e)$ does not contain $u_{1}u_{3}$. If $u_{4}u_{5}\in{\rm cl}((E_{0}\cup
F)+e)\setminus{\rm cl}(E_{0}\cup F)$, then $(E_{0}\cup F)+u_{4}u_{5}$ is
independent and ${\rm cl}((E_{0}\cup F)+u_{4}u_{5})={\rm cl}((E_{0}\cup
F)+e)$. This would imply that $(E_{0}\cup F)+u_{1}u_{3}+u_{4}u_{5}$ is
independent and contradict Claim 6.10. Hence $u_{4}u_{5}\in{\rm cl}(E_{0}\cup
F)$.

Suppose next that $u_{4}u_{5}\in{\rm cl}(E_{0}\cup F)\setminus{\rm
cl}(E_{0})$, i.e., $u_{4}u_{5}\in[F]$. Then $F$ is influential and so, by the
hypothesis, $F+e$ is a stabilizer. Hence ${\rm cl}((E_{0}\cup F)+e)={\rm
cl}(E_{0}\cup F_{v})={\rm cl}(E_{0}+f_{1}+f_{2}+u_{4}u_{5})$ holds for some
edges $f_{1},f_{2}\in F_{v}$. Then $E_{0}+f_{1}+f_{2}+u_{4}u_{5}+u_{1}u_{3}$
is independent and we again contradict Claim 6.10. Hence $u_{4}u_{5}\in{\rm
cl}(E_{0})$.

By applying the same argument to the complete graph on
$\\{u_{1},u_{2},u_{4},u_{5}\\}$, we also get $u_{3}u_{4}\in{\rm cl}(E_{0})$ or
$u_{3}u_{5}\in{\rm cl}(E_{0})$. (Specifically, we have $u_{3}u_{4}\in{\rm
cl}(E_{0})$ when $u_{1}u_{5}\notin{\rm cl}(E_{0}+f+e)$ or
$u_{2}u_{5}\notin{\rm cl}((E_{0}\cup F)+e)$ holds, and we have
$u_{3}u_{5}\in{\rm cl}(E_{0})$ when $u_{1}u_{4}\notin{\rm cl}((E_{0}\cup
F)+e)$ or $u_{2}u_{4}\notin{\rm cl}((E_{0}\cup F)+e)$ holds.) ∎

Recall that an edge $f\in F_{v}$ is said to be very good if
$\\{f,f^{\prime}\\}$ is a good pair for every $f^{\prime}\in
F_{v}\setminus\\{f\\}$. In order to apply Claim 6.13 for a given edge $e\in
K_{u}$, we need to find a good pair $F\subset F_{v}$ such that $(E_{0}\cup
F)+e$ is independent. The following claim shows we can do this under a mild
assumption.

######  Claim 6.16.

Let $e\in K_{u}\setminus{\rm cl}(E_{0})$, and suppose that $e\notin[f]$ for
some very good edge $f\in F_{v}$. Then there is a good pair $F\in{F_{v}\choose
2}$ such that $(E_{0}\cup F)+e$ is independent.

###### Proof.

Let $F_{v}=\\{f_{1},f_{2},f_{3}\\}$, and suppose that an edge $e\in
K_{u}\setminus{\rm cl}(E_{0})$ satisfies $e\notin[f_{1}]$ for a very good edge
$f_{1}$. Since $e\notin[f_{1}]$, $E_{0}+f_{1}+e$ is independent. As $f_{1}$ is
very good, $\\{f_{1},f_{2}\\}$ and $\\{f_{1},f_{3}\\}$ are both good. Hence,
if no good pair has the desired property, then $\\{f_{2},f_{3}\\}\subset{\rm
cl}(E_{0}+f_{1}+e)$. By Claim 6.4, $E_{0}+f_{1}+f_{2}$ is independent. Since
$f_{2}\in{\rm cl}(E_{0}+f_{1}+e)$, this gives ${\rm cl}(E_{0}+f_{1}+e)={\rm
cl}(E_{0}+f_{1}+f_{2})$, and $f_{3}\in{\rm cl}(E_{0}+f_{1}+f_{2})$ follows
since $f_{3}\in{\rm cl}(E_{0}+f_{1}+e)$. This would contradict Claim 6.4. ∎

Our next claim extends Claim 6.14. (Note that $F$ is not required to be a good
pair in the following claim.)

######  Claim 6.17.

${\rm cl}(E_{0}\cup F_{v})\cap K_{u}$ has no copy of $K_{4}$ and, for any
stabilizer $F+e$, ${\rm cl}((E_{0}\cup F)+e)\cap K_{u}$ has no copy of
$K_{4}$.

###### Proof.

Suppose that a copy of $K_{4}$ exists in ${\rm cl}(E_{0}\cup F_{v})\cap
K_{u}$. By Claim 6.7 we can choose a very good edge $f$ from $F_{v}$. Then
Claim 6.8 implies that ${\rm cl}(E_{0}+f)\cap K_{u}$ has no copy of $K_{4}$.
Hence there is an edge $e$ in the copy of $K_{4}$ with $e\notin{\rm
cl}(E_{0}+f)$. By Claim 6.16, there exists a good pair $F$ of edges in $F_{v}$
such that $(E_{0}\cup F)+e$ is independent. Since $e\in{\rm cl}(E_{0}\cup
F_{v})$ and $(E_{0}\cup F)+e$ is independent, we have $F_{v}\subset{\rm
cl}(E_{0}\cup F_{v})={\rm cl}((E_{0}\cup F)+e)$. (Note that $E_{0}\cup F_{v}$
is independent by Claim 6.4.) Now $F_{v}\subset{\rm cl}((E_{0}\cup F)+e)$
implies that $F+e$ is a stabilizer while ${\rm cl}(E_{0}\cup F_{v})={\rm
cl}((E_{0}\cup F)+e)$ implies that ${\rm cl}((E_{0}\cup F)+e)$ has a copy of
$K_{4}$. This contradicts Claim 6.14, and completes the proof of the first
part of the claim. The second part now follows from the fact that ${\rm
cl}(E_{0}\cup F_{v})={\rm cl}((E_{0}\cup F)+e)$ when $F+e$ is a stabilizer. ∎

######  Claim 6.18.

Let $e=u_{i}u_{j}\in K_{u}\setminus{\rm cl}(E_{0})$ be such that $e\notin[f]$
for some very good edge $f\in F_{v}$. Then ${\rm cl}(E_{0})$ contains at least
two edges of the triangle on $N_{G}(u_{0})\setminus\\{u_{i},u_{j}\\}$.

###### Proof.

We may assume, without loss of generality, that $e=u_{1}u_{2}$. Suppose that
two edges on $\\{u_{3},u_{4},u_{5}\\}$ are missing in ${\rm cl}(E_{0})$. By
symmetry, we may assume that $u_{3}u_{5}$ and $u_{4}u_{5}$ are missing.

We first show that for any $F\in{F_{v}\choose 2}$ with $(E_{0}\cup F)+e$
independent, we have

$\\{u_{1}u_{2},u_{1}u_{3},u_{1}u_{4},u_{2}u_{3},u_{2}u_{4},u_{3}u_{4},u_{3}u_{5},u_{4}u_{5}\\}\subset{\rm
cl}((E_{0}\cup F)+e).$ (56)

To see this, choose an $F\in{F_{v}\choose 2}$ such that $(E_{0}\cup F)+e$ is
independent. By Claim 6.11, ${\rm cl}((E_{0}\cup F)+e)$ contains a triangle on
$\\{u_{3},u_{4},u_{5}\\}$. To show that
$\\{u_{1}u_{2},u_{1}u_{3},u_{1}u_{4},u_{2}u_{3},u_{2}u_{4}\\}$ is contained in
${\rm cl}((E_{0}\cup F)+e)$, we first prove:

$\begin{split}&\text{ if $u_{k}u_{l}\notin{\rm cl}(E_{0})$ for some
$k,l\in\\{3,4,5\\}$, then}\\\ &\text{${\rm cl}((E_{0}\cup F)+e)$ contains a
triangle on $N(u_{0})\setminus\\{u_{k},u_{l}\\}$.}\end{split}$ (57)

This follows from Claim 6.11 if $u_{k}u_{l}\not\in{\rm cl}(E_{0}\cup F)$.
Hence we assume $u_{k}u_{l}\in{\rm cl}(E_{0}\cup F)\setminus{\rm
cl}(E_{0})=[F]$. By Claim 6.4, the unique edge $f^{\prime}$ in $F_{v}\setminus
F$ satisfies $f^{\prime}\notin[F]$. Also, since $u_{k}u_{l}\in[F]$, we can
choose $f^{\prime\prime}\in F$ such that ${\rm cl}(E_{0}\cup F)={\rm
cl}(E_{0}+f^{\prime\prime}+u_{k}u_{l})$. Since $f^{\prime}\notin{\rm
cl}(E_{0}\cup F)$, this implies that
$(E_{0}\cup\\{f^{\prime},f^{\prime\prime}\\})+u_{k}u_{l}$ is independent. If
$e=u_{1}u_{2}\notin{\rm
cl}((E_{0}\cup\\{f^{\prime},f^{\prime\prime}\\})+u_{k}u_{l})$, then
$(E_{0}\cup\\{f^{\prime},f^{\prime\prime}\\})+u_{k}u_{l}+e$ would be
independent, which contradicts Claim 6.10. Hence $e\in{\rm
cl}((E_{0}\cup\\{f^{\prime},f^{\prime\prime}\\})+u_{k}u_{l})$. As
$[\\{f^{\prime\prime},u_{k}u_{l}\\}]=[F]$ and $(E_{0}\cup F)+e$ is
independent, we have ${\rm
cl}((E_{0}\cup\\{f^{\prime},f^{\prime\prime}\\})+u_{k}u_{l})={\rm
cl}((E_{0}\cup F)+e)$. By Claim 6.11, ${\rm
cl}((E_{0}\cup\\{f^{\prime},f^{\prime\prime}\\})+u_{k}u_{l})$ contains a