# Effects of edge addition or removal on the nullity of a graph in the Lights
Out game

Ahmet Batal  Department of Mathematics
Izmir Institute of Technology
Izmir, TURKEY<EMAIL_ADDRESS>
###### Abstract.

Lights out is a game which can be played on any graph $G$. Initially we have a
configuration which assigns one of the two states on or off to each vertex.
The aim of the game is to turn all vertices to off state for an initial
configuration by activating some vertices where each activation switches the
state of the vertex and all of its neighbors. If the aim of the game can be
accomplished for all initial configurations then $G$ is called always
solvable. We call the dimension of the kernel of the closed neighborhood
matrix of the graph over the field $\mathbb{Z}_{2}$, nullity of $G$. It turns
out that $G$ is always solvable if and only if its nullity is zero. We
investigate the problem of how nullity changes when an edge is added to or
removed from a graph. As a result we characterize always solvable graphs. We
also showed that for every graph with positive nullity there exists an edge
whose removal decreases the nullity. Conversely, we showed that for every
always solvable graph which is not an even graph with odd order, there exists
an edge whose addition increases the nullity.

###### Key words and phrases:

Lights Out, all-ones problem, odd dominating set, parity domination, parity
dimension.

##  1\. Introduction

Lights out is a game which can be played on any undirected simple graph
$G(V,E)$. The rules of the game are as follows. Initially every vertex has one
of the two states _on_ or _off_. Every push on a vertex switches the state of
the vertex and all of its neighbors. This push is called _the activation of
the vertex_. The aim of the game is to turn all vertices to _off_ state by
applying an activation pattern. It can be easily observed that the order of
the activations or the act of activating a vertex more than once does not have
any importance. Therefore, any activation pattern can be identified by the set
of activated vertices. On the other hand, any initial configuration can be
identified by the set of _on_ state vertices. Note also that there is a one to
one correspondence between the subsets of $V(G)$ and elements of
$\mathbb{Z}_{2}^{n}$ where $n$ is the order of $V(G)$. Indeed, if we enumerate
$V(G)$ as $V(G)=\\{v_{1},...,v_{n}\\}$ then every set $S$ can be characterized
by its characteristic column vector
$\mathbf{x}_{S}=(s_{1},...,s_{n})^{t}\in\mathbb{Z}_{2}^{n},$ where
$\mathbf{x}_{S}(v_{i}):=s_{i}=1$ if $v_{i}\in S$, and $s_{i}=0$ otherwise.
Conversely, every element $\mathbf{x}$ of $\mathbb{Z}_{2}^{n}$ is the
characteristic vector of its support set which consists of those vertices $v$
such that $\mathbf{x}(v)=1$. Hence any activation pattern and initial
configuration can be identified by the vectors of $\mathbb{Z}_{2}^{n}$ as
well.

If an activation pattern set $P$ (activation pattern vector $\mathbf{p}$)
turns all vertices to off state for a given initial configuration set $C$
(initial configuration vector $\mathbf{c}$) , then $C$ ($\mathbf{c}$) is
called solvable and $P$ ($\mathbf{p}$) is called a solving pattern for $C$
($\mathbf{c}$). We may also say $P$ solves $C$ ($\mathbf{p}$ solves
$\mathbf{c}$). The graph $G$ is called _always solvable_ if every
configuration is solvable.

For a vertex $v$, the set $N[v]=\\{u\in V\;|\;u=v\;\text{or}\;u\;\text{is
adjacent to}\;v\\}$ is called _the closed neighborhood set of vertex_ $v$.
Observe that $P$ solves $C$ if and only if $N[v]\cap P$ is odd for all $v\in
C$ and even otherwise. We define the dot product between two vectors
$\mathbf{x}$, $\mathbf{y}\in\mathbb{Z}_{2}^{n}$ as
$\mathbf{x}\cdot\mathbf{y}:=\mathbf{x}^{t}\mathbf{y}$. Then, the above
observation can be rephrased as $P$ solves $C$ if and only if
$\mathbf{x}_{N[v]}\cdot\mathbf{x}_{P}=1$ for all $v\in C$ and $0$ otherwise.
As it is first observed by Sutner [11],[12], this is equivalent to say that
$P$ solves $C$ if and only if

(1) $N\mathbf{x}_{P}=\mathbf{x}_{C}$

over the field $\mathbb{Z}_{2}$, where $N:=N(G)$ is the _the closed adjacency
matrix of_ $G$ whose $i$th column (equivalently row) is the characteristic
vector of $N[v_{i}]$.

Let us denote the kernel of $N$ by $Ker(N)$. Elements of $Ker(N)$ are called
_null patterns_. $\nu(G):=dim(Ker(N(G))$ is called the nullity of $G$. The
above formulation (1) between an initial configuration and its solving pattern
leads us several observations [11],[12],[2]:

(_O 1_) A graph $G$ is always solvable _iff_ $\nu(G)=0$.

(_O 2_) Number of solving patterns for a given configuration is $2^{\nu(G)}$.
Indeed, if $\mathbf{p}$ solves $\mathbf{c}$, then
$\mathbf{p}+\boldsymbol{\ell}$ solves $\mathbf{c}$ as well for every null
pattern $\boldsymbol{\ell}$.

(_O 3_) A configuration vector (set) is solvable _iff_ it (its characteristic
vector) is orthogonal to every null pattern.

Suppose there is a vector $\mathbf{s}$ solving the all-ones configuration
$\mathbf{1}:=(1,...,1)^{t}$. Then, the support set $S$ of $\mathbf{s}$ is an
_odd dominating set_ , i.e.; $N[v]\cap S$ is odd for all $v\in V$. Therefore,
we call $\mathbf{s}$ an _odd dominating pattern_. Interestingly, every graph
has an odd dominating pattern, or equivalently all-ones configuration
$\mathbf{1}$ is solvable in every graph [11] (see also [6], [7], [9]).

How the nullity of a graph change when a vertex is removed or what the nullity
of the emergent graph becomes when two graphs are joined together by a single
or multiple edges was investigated by several authors [3], [10], [8], [4],
[5]. However, as far as we know, until now there has been no study which
investigates how nullity changes when an edge is added to or removed from a
graph. In this paper we fill this gap. Indeed we do this in a more general
context. To understand the generality of our context let $G$ be a graph,
$A_{1}$, $A_{2}$ be two disjoint subsets of $V(G)$. Then we define the
following operation on $G$. For every pair of vertices $u\in A_{1}$ and $v\in
A_{2}$ we add the edge $uv$ (the edge joining $u$ and $v$) to $G$ if $u$ and
$v$ are not adjacent and we remove the edge $uv$ from $G$ if $u$ and $v$ are
adjacent. So if $A_{1}$ and $A_{2}$ consists of single vertices, then the
operation corresponds to simple edge removal or addition, depending on whether
$u$ and $v$ are adjacent in $G$ or not. Then we investigate how nullity
changes when this operation is applied to the graph under different scenarios
as we stated in Proposition 2.9 through Proposition 2.20. The results are
summarized in Table 1. These results enable us to obtain important corollaries
such as a characterization of always solvable graphs as we stated in Theorem
3.9. Until now, characterizations of always solvable trees were only known
[1], [3], [5]. Therefore, Theorem 3.9 gains importance by being the first
example of a characterization of always solvable graphs. Moreover, we proved
in Theorem 3.1 that for a graph with nonzero nullity, there exists always an
edge whose removal decreases the nullity. Conversely, we showed in Theorem 3.5
that if an always solvable graph is not an even graph with odd order, then
there exists an edge whose addition increases the nullity.

##  2\. Change of the nullity under the general edge addition and removal
operation

######  Lemma 2.1.

Let $\mathbf{x}$ satisfy $\mathbf{x}\cdot\boldsymbol{\ell_{0}}=1$ for some
null pattern $\boldsymbol{\ell_{0}}$. Then,
$\mathbf{x}\cdot\boldsymbol{\ell}=1$ for exactly half of the null patterns
$\boldsymbol{\ell}$.

###### Proof.

Equality of the number of null patterns $\boldsymbol{\ell}$ satisfying
$\mathbf{x}\cdot\boldsymbol{\ell}=0$ and $\mathbf{x}\cdot\boldsymbol{\ell}=1$
follows from the fact that if a null pattern $\boldsymbol{\ell}$ satisfies
$\mathbf{x}\cdot\boldsymbol{\ell}=0$, then the null pattern
$\boldsymbol{\ell}+\boldsymbol{\ell_{0}}$ satisfies
$\mathbf{x}\cdot(\boldsymbol{\ell}+\boldsymbol{\ell_{0}})=1$; and if a null
pattern $\boldsymbol{\ell}$ satisfies $\mathbf{x}\cdot\boldsymbol{\ell}=1$,
then the null pattern $\boldsymbol{\ell}+\boldsymbol{\ell_{0}}$ satisfies
$\mathbf{x}\cdot(\boldsymbol{\ell}+\boldsymbol{\ell_{0}})=0$. ∎

Lemma 2.1, together with (_O 2_) and (_O 3_) gives us the following
proposition.

######  Proposition 2.2.

Let $\mathbf{c}$ be a solvable configuration on a graph $G$ and $A$ be a set.
Then, $A$ is not solvable if and only if $\mathbf{x}_{A}\cdot\mathbf{p}=1$ for
exactly half of the solving patterns $\mathbf{p}$ for $\mathbf{c}$. $A$ is
solvable if and and only if either

Case i) $\mathbf{x}_{A}\cdot\mathbf{p}=1$ for all solving patterns
$\mathbf{p}$ for $\mathbf{c}$, or

Case ii) $\mathbf{x}_{A}\cdot\mathbf{p}=0$ for all solving patterns
$\mathbf{p}$ for $\mathbf{c}.$

Motivating ourselves by the above proposition we make the following
definition.

######  Definition 2.3.

We say a set $A$ is half odd activated ($HO$) if it is not solvable. If $A$ is
solvable, for a given solvable configuration $\mathbf{c}$, we say $A$ is
$\mathbf{c}$-always odd activated ($\mathbf{c}$-$AO$), $\mathbf{c}$-never odd
activated ($\mathbf{c}$-$NO$) if Case i) or Case ii) holds, respectively. In
the case where $\mathbf{c}=\mathbf{1}$, instead of saying $A$ is
$\mathbf{1}$-always odd activated, $\mathbf{1}$-never odd activated; we simply
say $A$ is always odd activated ($AO$), never odd activated ($NO$),
respectively. Further, we say a vertex $v$ is half activated, always
activated, or never activated if $\\{v\\}$ is half odd activated, always odd
activated, or never odd activated, respectively.

######  Remark 2.4.

Definitions of half activated, always activated and never activated vertices
coincide with the definitions in [5]. Indeed, by (_O 3_) we see that, for a
vertex $u$, $\\{u\\}$ is not solvable if and only if
$\boldsymbol{\ell}(u)=\mathbf{x}_{\\{u\\}}\cdot\boldsymbol{\ell}=1$ for some
null pattern $\boldsymbol{\ell}$.

For a given vector $\mathbf{x}$, let
$\overline{\mathbf{x}}:=\mathbf{x}+\mathbf{1}$.

######  Lemma 2.5.

A vector $\mathbf{x}$ (a set $A$) is solvable if and only if
$\overline{\mathbf{x}}$ ($A^{c}$) is solvable.

###### Proof.

Note that if a configuration $\mathbf{x}$ is solvable, then
$\overline{\mathbf{x}}=\mathbf{1}+\mathbf{x}$ is solvable since it is the sum
of two solvable configurations. Converse also holds since
$\overline{\overline{\mathbf{x}}}=\mathbf{x}$. Note also that if $\mathbf{x}$
is the characteristic vector of a set $A$, then $\overline{\mathbf{x}}$ is the
characteristic vector of $A^{c}$. ∎

######  Lemma 2.6.

For a given graph $G$ let the configuration $\mathbf{x}$ be solvable. Then
$\mathbf{x}\cdot\mathbf{p}=0$ for all solving patterns $\mathbf{p}$ for
$\overline{\mathbf{x}}$.

###### Proof.

Let $N$ be the closed neighborhood matrix of $G$, $\mathbf{p}$ be a solving
patterns for $\overline{\mathbf{x}}$, and $\mathbf{s}$ be an odd dominating
pattern of $G$. Then
$N(\mathbf{p}+\mathbf{s})=\overline{\mathbf{x}}+\mathbf{1}=\mathbf{x}$.
Moreover $N$ can be written as $N=I+L+L^{t}$ where $I$ is the identity matrix
and $L$ is a lower triangular matrix with $0$ diagonal entries. Consequently,

$\displaystyle\mathbf{x}\cdot\mathbf{p}$
$\displaystyle=N(\mathbf{p}+\mathbf{s})\cdot\mathbf{p}$
$\displaystyle=(N(\mathbf{p}+\mathbf{s}))^{t}\mathbf{p}$
$\displaystyle=\mathbf{p}^{t}N\mathbf{p}+(N\mathbf{s})^{t}\mathbf{p}$ (2)
$\displaystyle=\mathbf{p}^{t}\mathbf{p}+\mathbf{p}^{t}L\mathbf{p}+\mathbf{p}^{t}L^{t}\mathbf{p}+\mathbf{1}^{t}\mathbf{p}$
$\displaystyle=\mathbf{p}\cdot\mathbf{p}+\mathbf{p}\cdot(L\mathbf{p})+(L\mathbf{p})\cdot\mathbf{p}+\mathbf{1}\cdot\mathbf{p}$
$\displaystyle=(\mathbf{p}+\mathbf{1})\cdot\mathbf{p}$
$\displaystyle=\overline{\mathbf{p}}\cdot\mathbf{p}$ $\displaystyle=0.$

∎

######  Lemma 2.7.

A set $A$ is $AO$ ($NO$) if and only if $A$ is $\mathbf{x}_{A}$-$AO$
($\mathbf{x}_{A}$-$NO$).

###### Proof.

Let $\mathbf{s}$ be an odd dominating pattern and $\mathbf{r}$ be a solving
pattern for $\mathbf{x}_{A}$. So $\mathbf{s}+\mathbf{r}$ solves
$\mathbf{1}+\mathbf{x}_{A}=\overline{\mathbf{x}_{A}}$. By Lemma 2.6,
$\mathbf{x}_{A}\cdot(\mathbf{s}+\mathbf{r})=0$. Hence,
$\mathbf{x}_{A}\cdot\mathbf{s}=\mathbf{x}_{A}\cdot\mathbf{r}$. ∎

######  Lemma 2.8.

Let $G$ be a graph; $A_{1}$, $A_{2}$ be two disjoint solvable subsets of
$V(G)$. Then the followings hold.

i) If $A_{1}$ and $A_{2}$ are both $AO$ or both $NO$, then $A_{1}$ is
$\overline{\mathbf{x}_{A_{2}}}$-$NO$ if and only if $A_{2}$ is
$\overline{\mathbf{x}_{A_{1}}}$-$NO$.

ii) If $A_{1}$ is $AO$ and $A_{2}$ is $NO$, then $A_{1}$ is
$\overline{\mathbf{x}_{A_{2}}}$-$NO$ if and only if $A_{2}$ is
$\overline{\mathbf{x}_{A_{1}}}$-$AO$.

###### Proof.

Let $\mathbf{p_{1}}$, $\mathbf{p_{2}}$ be solving patterns for
$\overline{\mathbf{x}_{A_{1}}}$, $\overline{\mathbf{x}_{A_{2}}}$,
respectively. Let us first assume that $A_{1}$ and $A_{2}$ are both $AO$ or
both $NO$. Then $A_{1}\cup A_{2}$ is $NO$ since $A_{1}$ and $A_{2}$ are
disjoint. By Lemma 2.7 it is $\mathbf{x}_{A_{1}\cup A_{2}}$-$NO$. On the other
hand,
$N(\mathbf{p_{1}}+\mathbf{p_{2}})=\overline{\mathbf{x}_{A_{1}}}+\overline{\mathbf{x}_{A_{2}}}=\mathbf{x}_{A_{1}}+\mathbf{1}+\mathbf{x}_{A_{1}}+\mathbf{1}=\mathbf{x}_{A_{1}\cup
A_{2}}$. Hence, $\mathbf{x}_{A_{1}\cup
A_{2}}\cdot(\mathbf{p_{1}}+\mathbf{p_{2}})=0$. Explicitly this means
$\mathbf{x}_{A_{1}}\cdot\mathbf{p_{1}}+\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}+\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}+\mathbf{x}_{A_{2}}\cdot\mathbf{p_{2}}=0$.
By Lemma 2.6,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p_{1}}=\mathbf{x}_{A_{2}}\cdot\mathbf{p_{2}}=0$.
So
$\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}+\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}=0$,
which implies
$\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}=\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}$.

In the second case where $A_{1}$ is $AO$ and $A_{2}$ is $NO$, the proof
follows the same lines as in the above case but this time $A_{1}\cup A_{2}$ is
$AO$ which leads us
$\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}+\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}=1$.
Hence,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}=1-\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}$.
∎

Let $G$ be a graph, $A_{1}$, $A_{2}$ be two disjoint subsets of $V(G)$. We
define the graph $G^{*}$ as the resulting graph of the following operation.
For every pair of vertices $u\in A_{1}$ and $v\in A_{2}$ we add the edge $uv$
to $G$ if $u$ and $v$ are not adjacent and we remove the edge $uv$ from $G$ if
$u$ and $v$ are adjacent. Let $N$, $N^{*}$ be the closed neighborhood matrices
of $G$, $G^{*}$, respectively. Let $V(G)=\\{v_{1},...,v_{n}\\}$. Realize that
the relation between the closed neighborhood matrices $N$ and $N^{*}$ is given
by $N^{*}=N+J$ where $J$ is the matrix with entries

(5) $\displaystyle
J_{ij}=\left\\{\begin{array}[]{cc}1&\;\;\text{if}\;\;\;\;v_{i}\in
A_{1},\;v_{j}\in A_{2}\;or\;v_{j}\in A_{1},\;v_{i}\in A_{2}\\\
0&\;\;\text{otherwise}\\\ \end{array}\right\\},$

This implies that for any pattern $\mathbf{p}$ we have

(6)
$N^{*}\mathbf{p}=N\mathbf{p}+(\mathbf{x}_{A_{1}}\cdot\mathbf{p})\mathbf{x}_{A_{2}}+(\mathbf{x}_{A_{2}}\cdot\mathbf{p})\mathbf{x}_{A_{1}}.$

Let $\Delta\nu=\nu(G^{*})-\nu(G)$. In the following propositions we state
solving patterns for which configurations in $G$ correspond to an odd
dominating pattern of $G^{*}$ and how $\Delta\nu$ and activation types of
$A_{1}$ and $A_{2}$ change under different cases.

In the proofs of the following propositions we reserve the notations
$\mathbf{p_{1}}$ and $\mathbf{p_{2}}$ for arbitrary solving patterns for
$\overline{\mathbf{x}_{A_{1}}}$, $\overline{\mathbf{x}_{A_{2}}}$,
respectively; and we reserve the notations $\mathbf{r_{1}}$ and
$\mathbf{r_{2}}$ for arbitrary solving patterns for $\mathbf{x}_{A_{1}}$,
$\mathbf{x}_{A_{2}}$, respectively.

######  Proposition 2.9.

Let $A_{1}$ and $A_{2}$ be $NO$ sets in $G$. Also assume that $A_{2}$ is
$\overline{\mathbf{x}_{A_{1}}}$-$NO$ in $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\mathbf{1}.$ Moreover, $A_{1}$ and $A_{2}$ are $NO$ in
$G^{*}$ and $\Delta\nu=0$.

###### Proof.

Let $N^{*}\mathbf{p}=\mathbf{1}$. First, assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0\;\text{and}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$.
Then, by (6), $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}.$ By the assumption
of the proposition $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$, which is a
contradiction.

Second, assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1\;\text{and}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$
Then, by (6), $N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}.$ By Lemma 2.8,
$A_{2}$ is $\overline{\mathbf{x}_{A_{1}}}$-$NO$ is equivalent to say $A_{1}$
is $\overline{\mathbf{x}_{A_{2}}}$-$NO$. Hence
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$, which is a contradiction.

Third assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1\;\text{and}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$
Then, by (6), $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{2}}$ , which means
$\mathbf{p}=\mathbf{p_{1}}+\mathbf{r_{2}}$.

(7)
$1=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}+\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}$

by the assumption. On the other hand, $A_{2}$ is $NO$ implies $A_{2}$ is
$\mathbf{x}_{A_{2}}$-$NO$ by Lemma 2.7. Hence
$\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=0$, which contradicts with (7).

Consequently, the only possibility is that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0\;\text{and}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0,$
which, by (6), gives $N\mathbf{p}=\mathbf{1}$.

Conversely, let $N\mathbf{p}=\mathbf{1}$. Then $\mathbf{p}$ is an odd
dominating pattern of $G$. Since $A_{1}$ and $A_{2}$ are $NO$ in $G$, this
gives
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0\;\text{and}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$,
which together with (6), implies $N^{*}\mathbf{p}=\mathbf{1}$.

Since the odd dominating patterns of $G$ and $G^{*}$ are identical, the
activation types of sets does not change. Hence $A_{1}$ and $A_{2}$ are NO in
$G^{*}$. Also the fact that the number of odd dominating patterns of $G$ and
$G^{*}$ are the same, implies $\nu(G)=\nu(G^{*})$ by (_O 2_). Hence
$\Delta\nu=0$.

∎

######  Proposition 2.10.

Let $A_{1}$ and $A_{2}$ be $NO$ sets in $G$. Also assume that $A_{2}$ is
$\overline{\mathbf{x}_{A_{1}}}$-$AO$ in $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\mathbf{1}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}.$ Moreover, $A_{1}$ and $A_{2}$ are $HO$ in $G^{*}$, and
$\Delta\nu=2$.

###### Proof.

Let $N^{*}\mathbf{p}=\mathbf{1}$. Then, by (6), we have

$N\mathbf{p}=\mathbf{1}+(\mathbf{x}_{A_{1}}\cdot\mathbf{p})\mathbf{x}_{A_{2}}+(\mathbf{x}_{A_{2}}\cdot\mathbf{p})\mathbf{x}_{A_{1}}.$

Hence, depending on the the value of $\mathbf{x}_{A_{1}}\cdot\mathbf{p}$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}$, one of the four cases
$N\mathbf{p}=1,\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}},\;N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}},\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}$ must hold.

Conversely, let us first assume that $N\mathbf{p}=\mathbf{1}$. Then by
assumption
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$. By
(6), $N^{*}\mathbf{p}=\mathbf{1}$.

Second, let $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}.$ Then by assumption,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$. Moreover, by Lemma 2.6,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$. Thus, by (6),
$N^{*}\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{1}}=\mathbf{1}$.

Third, let $N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}.$ By assumption and
Lemma 2.8, $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$. Moreover, by Lemma 2.6,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$. Then, by (6),
$N^{*}\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}+\mathbf{x}_{A_{2}}=\mathbf{1}$.

Lastly, let $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{2}}=\mathbf{x}_{A_{1}}+\overline{\mathbf{x}_{A_{2}}}.$
Hence
$\mathbf{p}=\mathbf{p_{1}}+\mathbf{r_{2}}=\mathbf{p_{2}}+\mathbf{r_{1}}$. Note
that by assumption $A_{1}$ and $A_{2}$ are $NO$. By Lemma 2.7, $A_{1}$ and
$A_{2}$ are $\mathbf{x}_{A_{1}}$-$NO$ and $\mathbf{x}_{A_{2}}$-$NO$,
respectively. Hence,
$\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=0$.
Moreover, by assumption and Lemma 2.8,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}=\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}=1$.
Then,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}+\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=1$,
and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}+\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=1$.
Consequently, by (6), $N^{*}\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}+\overline{\mathbf{x}_{A_{1}}}+\overline{\mathbf{x}_{A_{2}}}=\mathbf{1}.$

Note that there exist $2^{\nu(G)}$ patterns $\mathbf{p}$ for each case
$N\mathbf{p}=1,\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}},\;N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}},\;\text{and}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}$. So there exist total of $2^{\nu(G)+2}$ patterns satisfying one of
the four cases. On the other hand there exist $2^{\nu(G^{*})}$ odd dominating
patterns of $G^{*}$. Hence, $\nu(G^{*})=\nu(G)+2$, which implies
$\Delta\nu=2$. Moreover, $\mathbf{x}_{A_{1}}\cdot\mathbf{p}$ is zero in the
first two cases and one in the last two cases, which makes $A_{1}$ a $HO$ set
in $G^{*}$. Similarly, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}$ is zero in the
first and third cases and one in the second and fourth cases. Hence, $A_{2}$
is $HO$ in $G^{*}$ as well.

∎

######  Proposition 2.11.

Let $A_{1}$ be a $NO$ and $A_{2}$ be a $AO$ set in $G$. Also assume that
$A_{2}$ is $\overline{\mathbf{x}_{A_{1}}}$-$NO$ in $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}.$ Moreover, $A_{1}$ is a $AO$ and $A_{2}$ is a $HO$ set in $G^{*}$,
and $\Delta\nu=1$.

###### Proof.

Let $N^{*}\mathbf{p}=\mathbf{1}$. Assume first that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$. Then,
by (6), we have $N\mathbf{p}=\mathbf{1}$. But then
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ since $A_{2}$ is an $AO$ set in $G$,
which is a contradiction.

Assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$. By (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$. Then
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ by the assumption of the proposition,
which is a contradiction. Hence
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}.$

Conversely, assume $N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$. Then
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ by the assumption of the proposition and
Lemma 2.8. Moreover, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ by Lemma 2.6.
Hence, by (6), $N^{*}\mathbf{p}=1$.

Assume $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{2}}=\overline{\mathbf{x}_{A_{2}}}+\mathbf{x}_{A_{1}}$.
Then $\mathbf{p}=\mathbf{p_{1}}+\mathbf{r_{2}}=\mathbf{p_{2}}+\mathbf{r_{1}}$.
Moreover, $\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}=1$ by the assumption of the
proposition and Lemma 2.8. In view of Lemma 2.7,
$\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=0$ since $A_{1}$ is a $NO$ set in $G$,
and $\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=1$ since $A_{2}$ is a $AO$ set in
$G$. Therefore,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}+\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=1$,
and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}+\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=1$.
Then, by (6), $N^{*}\mathbf{p}=1$.

There exist $2.2^{\nu(G)}$ patterns satisfying
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}},$ and there are $2^{\nu(G^{*})}$ odd dominating patterns of $G^{*}$.
Hence $\nu(G^{*})=\nu(G)+1$, which gives $\Delta\nu=1$.
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ in both cases
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}\;\text{and}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}},$ which makes $A_{1}$ an $AO$ set in $G^{*}$. On the other hand,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}$ is $0$ in the case
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$ and $1$ in the case
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$. Hence $A_{2}$ is a $HO$
set in $G^{*}$. ∎

######  Proposition 2.12.

Let $A_{1}$ be a $NO$ and $A_{2}$ be an $AO$ set in $G$. Also assume that
$A_{2}$ is $\overline{\mathbf{x}_{A_{1}}}$-$AO$ in $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}.$ Moreover, $A_{1}$ is a $NO$
and $A_{2}$ is an $AO$ set in $G^{*}$, and $\Delta\nu=0$.

###### Proof.

Let $N^{*}\mathbf{p}=1$. First assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$. Then, by (6), $N\mathbf{p}=1$. This
implies $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ by assumption, which is a
contradiction.
Second assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$. Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$. By assumption and Lemma 2.8,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0,$ which is a contradiction.
Third assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$. Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{2}}$, which implies
$\mathbf{p}=\mathbf{p_{1}}+\mathbf{r_{2}}$. Because $A_{2}$ is an $AO$ set in
$G$, $\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=1$ by Lemma 2.7. Thus,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}+\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=0$,
which is a contradiction.
So the only possible case is $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1,$ which by (6), gives
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$.

Conversely, if $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$, then
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ by assumption. Moreover,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ by Lemma 2.6. Thus, by (6),
$N^{*}\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{1}}=\mathbf{1}$.

There exist $2^{\nu(G)}$ patterns satisfying
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ and there are $2^{\nu(G^{*})}$ odd
dominating patterns of $G^{*}$. Hence $\nu(G^{*})=\nu(G)$, which gives
$\Delta\nu=0$. Moreover $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ in case of
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$. Hence $A_{1}$ is a $NO$ and
$A_{2}$ is an $AO$ set in $G^{*}$. ∎

######  Proposition 2.13.

Let $A_{1}$ and $A_{2}$ be two $AO$ sets in $G$. Also assume that $A_{2}$ is
$\overline{\mathbf{x}_{A_{1}}}$-$NO$ in $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}.$ Moreover, $A_{1}$
and $A_{2}$ are $AO$ sets in $G^{*}$ , and $\Delta\nu=0$.

###### Proof.

Let $N^{*}\mathbf{p}=1$. First assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$ Then,
by (6), $N\mathbf{p}=1$. Since $A_{1}$ is an $AO$ set in $G$ we must have
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$, which is a contradiction.

Second assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$ Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$. So, by the assumption of the
proposition $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0,$ which is a contradiction.

Third assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$ Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$. By the assumption of the
proposition and Lemma 2.8, $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$, which is a
contradiction.

So the last case where $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ is the only possible case, which leads
to $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ by (6).

Conversely, let $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{2}}=\overline{\mathbf{x}_{A_{2}}}+\mathbf{x}_{A_{1}}.$
Then,
$\mathbf{p}=\mathbf{p_{1}}+\mathbf{r_{2}}=\mathbf{p_{2}}+\mathbf{r_{1}}$. By
assumption $A_{1}$ and $A_{2}$ are $AO$. By Lemma 2.7, $A_{1}$ and $A_{2}$ are
$\mathbf{x}_{A_{1}}$-$AO$ and $\mathbf{x}_{A_{2}}$-$AO$, respectively. Hence,
$\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=1$.
Moreover, by assumption and Lemma 2.8,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}=\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}=0$.
Then,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}+\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=1$,
and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p_{1}}+\mathbf{x}_{A_{2}}\cdot\mathbf{r_{2}}=1$.
Consequently, by (6), $N^{*}\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}+\overline{\mathbf{x}_{A_{1}}}+\overline{\mathbf{x}_{A_{2}}}=\mathbf{1}.$

There exist $2^{\nu(G)}$ patterns satisfying
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ and there are
$2^{\nu(G^{*})}$ odd dominating patterns of $G^{*}$. Hence,
$\nu(G^{*})=\nu(G)$, which gives $\Delta\nu=0$. Moreover
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ in case of
$\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$. Therefore, $A_{1}$ and $A_{2}$ are
$AO$ sets in $G^{*}$. ∎

######  Proposition 2.14.

Let $A_{1}$ and $A_{2}$ be two $AO$ sets in $G$. Also assume that $A_{2}$ is
$\overline{\mathbf{x}_{A_{1}}}$-$AO$ in $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}.$
Moreover, $A_{1}$ and $A_{2}$ are $HO$ sets in $G^{*}$, and $\Delta\nu=1$.

###### Proof.

Let $N^{*}\mathbf{p}=1$. First assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$ Then,
by (6), $N\mathbf{p}=1$. Since $A_{1}$ is an $AO$ set in $G$, we must have
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$, which is a contradiction.

Second assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$ Then,
by (6), $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}=\overline{\mathbf{x}_{A_{2}}}+\mathbf{x}_{A_{1}}$. Thus,
$\mathbf{p}=\mathbf{p_{2}}+\mathbf{r_{1}}.$ By assumption of the proposition
and Lemma 2.8, $\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}=1$. Lemma 2.7 and the
fact that $A_{1}$ is an $AO$ set in $G$ imply
$\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=1.$ Thus,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{1}}\cdot\mathbf{p_{2}}+\mathbf{x}_{A_{1}}\cdot\mathbf{r_{1}}=1+1=0$,
which is a contradiction.

So either the case where $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ or the case where
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$
holds true, which, by (6), leads to
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ or
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$, respectively.

Conversely, assume first that $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$. By
the assumption of the proposition, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$ By
Lemma 2.6, $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0.$ Hence, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}+\mathbf{x}_{A_{2}}=\mathbf{1}$.

Second assume that $N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$. By the
assumption of the proposition and by Lemma 2.8,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1.$ By Lemma 2.6,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$ Hence, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}+\mathbf{x}_{A_{2}}=\mathbf{1}$.

There exist $2.2^{\nu(G)}$ patterns satisfying
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}},$
and there are $2^{\nu(G^{*})}$ odd dominating patterns of $G^{*}$. Hence
$\nu(G^{*})=\nu(G)+1$, which gives $\Delta\nu=1$.
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}$ is $0$ in the case
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ and $1$ in the case
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$, which makes $A_{1}$ a $HO$ set in
$G^{*}$. On the other hand, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}$ is $1$ in the
case $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ and $0$ in the case
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$. Hence, $A_{2}$ a $HO$ set in
$G^{*}$ as well.

∎

######  Proposition 2.15.

Let $A_{1}$ be a $NO$ and $A_{2}$ be a $HO$ set in $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\mathbf{1}\;\text{with}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0\;\text{or}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}\;\text{with}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$
Moreover, $A_{1}$ is a $NO$ and $A_{2}$ is a $HO$ set in $G^{*}$, and
$\Delta\nu=0$.

###### Proof.

Let $N^{*}\mathbf{p}=1$. First assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$ Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$. By Lemma 2.5 $A_{2}$ is solvable,
which is a contradiction.

Second assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$ Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$. By Lemma 2.5,
$A_{1}\cup A_{2}$ is solvable, i.e.; it is not $HO$. On the other hand,
$A_{1}$ is $NO$ and $A_{2}$ is $HO$ imply $A_{1}\cup A_{2}$ is $HO$. Thus, we
have a contradiction.

So either
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0,$
which, by (6), implies $N\mathbf{p}=\mathbf{1}$ with
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$; or
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1,$ which, by (6), implies
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ with
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$.

Conversely, first assume that $N\mathbf{p}=\mathbf{1}$ with
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$. Since $A_{1}$ is $NO$ in $G$, we have
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$. Hence, by (6),
$N^{*}\mathbf{p}=\mathbf{1}$. Second assume that
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ with
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$. Then, by Lemma 2.6,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$. Thus, by (6),
$N^{*}\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{1}}=\mathbf{1}.$

Since $A_{2}$ is $HO$ in $G$, there are $2^{\nu(G)-1}$ patterns satisfying
$N\mathbf{p}=\mathbf{1}\;\text{with}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$,
and also there are $2^{\nu(G)-1}$ patterns satisfying
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}\;\text{with}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$
So there are $2^{\nu(G)}$ patterns satisfying one of the two cases. On the
other hand, there are $2^{\nu(G^{*})}$ odd dominating patterns of $G^{*}$.
Hence, $\nu(G^{*})=\nu(G)$, which gives $\Delta\nu=0$. In each case,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$, which makes $A_{1}$ a $NO$ set in
$G^{*}$. On the other hand, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ in the first
case and $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ in the second one, which makes
$A_{2}$ a $HO$ set in $G^{*}$. ∎

######  Proposition 2.16.

Let $A_{1}$ be an $AO$ and $A_{2}$ be a $HO$ set $G$. Then for any pattern
$\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}\;\text{with}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$
Moreover, $A_{1}$ is a $NO$ and $A_{2}$ is an $AO$ set $G^{*}$, and
$\Delta\nu=-1$.

###### Proof.

Let $N^{*}\mathbf{p}=1$. First assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$ Then,
by (6), $N\mathbf{p}=\mathbf{1}$. Then, $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$
since $A_{1}$ is $AO$, which is a contradiction.

Second assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0.$ Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{2}}}$. By Lemma 2.5, $A_{2}$ is
solvable, which is a contradiction.

Third assume that $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$ Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$. By Lemma 2.5,
$A_{1}\cup A_{2}$ is solvable. On the other hand, $A_{1}$ is $AO$ and $A_{2}$
is $HO$ imply $A_{1}\cup A_{2}$ is $HO$, which means it is not solvable. Thus,
we have a contradiction.

So the only possible case is $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1,$ which by (6), gives
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ with
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$.

Conversely assume that $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$ with
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$. By Lemma 2.6,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$. Hence, by (6),
$N^{*}\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}+\mathbf{x}_{A_{1}}=\mathbf{1}$.

Since $A_{2}$ is $HO$ in $G$, there are $2^{\nu(G)-1}$ patterns satisfying
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}\;\text{with}\;\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$,
On the other hand, there are $2^{\nu(G^{*})}$ odd dominating patterns of
$G^{*}$. Hence, $\nu(G^{*})=\nu(G)-1$, which gives $\Delta\nu=-1$. The above
equivalence shows that when $N^{*}\mathbf{p}=\mathbf{1}$,
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$, which makes $A_{1}$ a $NO$ and $A_{2}$
an $AO$ set $G^{*}$. ∎

######  Lemma 2.17.

Let $G$ be a graph, $\mathbf{c}$ be a solvable configuration in $G$ and $S$ be
the set of all solving patterns for $\mathbf{c}$ with $|S|=n$. Let $A_{1}$ and
$A_{2}$ be two disjoint HO sets in $G$. For $i\in\\{1,2\\}$, define the sets
$O_{i}=\\{\mathbf{p}\in S\;|\;\mathbf{x}_{A_{i}}\cdot\mathbf{p}=0\\}$ and
$I_{i}=\\{\mathbf{p}\in S\;|\;\mathbf{x}_{A_{i}}\cdot\mathbf{p}=1\\}$. Then,
$|O_{1}\cap O_{2}|=|I_{1}\cap I_{2}|,$ and $A_{1}\cup A_{2}$ is
$\mathbf{c}$-NO, HO, or $\mathbf{c}$-AO if and only if $|O_{1}\cap
O_{2}|=n/2,\;n/4,\;\text{or}\;0,$ respectively.

###### Proof.

First note that, by Proposition 2.2, $|O_{1}|=|I_{1}|=|O_{2}|=|I_{2}|=n/2$
since $A_{1}$ and $A_{2}$ are $HO$. Moreover,

$I_{1}=S\cap I_{1}=(O_{2}\cap I_{1})\cup(I_{2}\cap I_{1})$ $O_{2}=S\cap
O_{2}=(O_{1}\cap O_{2})\cup(I_{1}\cap O_{2}),$

which imply $n/2=|O_{2}\cap I_{1}|+|I_{2}\cap I_{1}|=|O_{1}\cap
O_{2}|+|I_{1}\cap O_{2}|$. Hence, $|O_{1}\cap O_{2}|=|I_{1}\cap I_{2}|.$ Let
$O_{12}:=\\{\mathbf{p}\in S\;|\;\mathbf{x}_{A_{1}\cup
A_{2}}\cdot\mathbf{p}=0\\}$. Since $\mathbf{x}_{A_{1}\cup
A_{2}}\cdot\mathbf{p}=\mathbf{x}_{A_{1}}\cdot\mathbf{p}+\mathbf{x}_{A_{2}}\cdot\mathbf{p}$,
we have $O_{12}=(O_{1}\cap O_{2})\cup(I_{1}\cap I_{2})$. Hence,
$|O_{12}|=|O_{1}\cap O_{2}|+|I_{1}\cap I_{2}|=2|O_{1}\cap O_{2}|$. Now, the
result follows by the fact that $A_{1}\cup A_{2}$ is $\mathbf{c}$-$NO$, $HO$,
or $\mathbf{c}$-$AO$ if and only if $|O_{12}|=n,\;n/2,\;\text{or}\;0,$
respectively.

∎

######  Proposition 2.18.

Let $A_{1}$, $A_{2}$, and $A_{1}\cup A_{2}$ be $HO$ sets in $G$. Then for any
pattern $\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\mathbf{1}$ with
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$.
Moreover, $A_{1}$ and $A_{2}$ are $NO$ sets in $G^{*}$ and $\Delta\nu=-2$.

###### Proof.

Let $N^{*}\mathbf{p}=\mathbf{1}$. Assume that
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1.$ Then, by (6),
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}}}$. By Lemma 2.5 $A_{1}$ is solvable,
which is a contradiction.

Assuming $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ leads to a similar contradiction.

Assuming $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ we obtain
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ by (6). Hence $A_{1}\cup
A_{2}$ is solvable, which is a contradiction.

So the only possible case is $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0,$ which by (6), gives
$N\mathbf{p}=\mathbf{1}$.

Conversely, if $\mathbf{p}$ satisfies the condition $N\mathbf{p}=\mathbf{1}$
with $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$ and
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ then we get $N^{*}\mathbf{p}=1$ by (6).

Note that the above condition on $\mathbf{p}$ is equivalent to say that
$\mathbf{p}\in O_{1}\cap O_{2}$, where $O_{1}$ and $O_{2}$ are the sets
defined as in Lemma 2.17 with $\mathbf{c}=\mathbf{1}$. If we denote the number
of odd dominating patterns of $G$ by $n$, then the number of patterns
satisfying the condition is $n/4$ by Lemma 2.17. This is equivalent to say
that $\Delta\nu=-2$ since the number of odd dominating patterns of $G$ and
$G^{*}$ are $2^{\nu(G)}$ and $2^{\nu(G^{*})}$, respectively.

Lastly, since
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ for
all odd dominating patterns $\mathbf{p}$ of $G^{*}$, we conclude that $A_{1}$
and $A_{2}$ are $NO$ in $G^{*}$.

∎

######  Proposition 2.19.

Let $A_{1}$, $A_{2}$ be $HO$, and $A_{1}\cup A_{2}$ be $AO$ sets in $G$. Then
for any pattern $\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ with
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$.
Moreover, $A_{1}$ and $A_{2}$ are $AO$ sets in $G^{*}$ and $\Delta\nu=-1$.

###### Proof.

Let $N^{*}\mathbf{p}=\mathbf{1}$. Assuming
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$
or $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ leads us to the contradictions as in the
proof of Proposition 2.18.

Assuming
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$, we
obtain $N\mathbf{p}=\mathbf{1}$ by (6). This gives $\mathbf{x}_{A_{1}\cup
A_{2}}\cdot\mathbf{p}=1$ since $A_{1}\cup A_{2}$ is $AO$ in $G$. However, by
assumption $\mathbf{x}_{A_{1}\cup
A_{2}}\cdot\mathbf{p}=\mathbf{x}_{A_{1}}\cdot\mathbf{p}+\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$,
which gives us a contradiction.

So the only possible case is
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1,$ which
by (6), gives $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$.

Conversely, if $\mathbf{p}$ satisfies the condition
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ with
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$, then
$N^{*}\mathbf{p}=\mathbf{1}$ by (6).

Note that the above condition on $\mathbf{p}$ is equivalent to say that
$\mathbf{p}\in I_{1}\cap I_{2}$, where $I_{1}$ and $I_{2}$ are the sets
defined as in Lemma 2.17 with $\mathbf{c}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}$. Note that $A_{1}\cup A_{2}$ is $\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}$-$NO$ by Lemma 2.6. Therefore, if we denote the number of patterns
satisfying $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ by $n$, then
the number of patterns satisfying the condition is $n/2$ by Lemma 2.17. This
is equivalent to say that $\Delta\nu=-1$ since the number of patterns
satisfying $N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ is
$2^{\nu(G)}$ and the number of odd dominating patterns of $G^{*}$ is
$2^{\nu(G^{*})}$.

Lastly, since
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ for
all odd dominating patterns $\mathbf{p}$ of $G^{*}$, we conclude that $A_{1}$
and $A_{2}$ are $AO$ in $G^{*}$. ∎

######  Proposition 2.20.

Let $A_{1}$, $A_{2}$ be $HO$, and $A_{1}\cup A_{2}$ be $NO$ sets in $G$. Then
for any pattern $\mathbf{p}$, $N^{*}\mathbf{p}=\mathbf{1}\;\text{if and only
if}\;N\mathbf{p}=\mathbf{1}$ with
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ or
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ with
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$.
Moreover, $A_{1}$ and $A_{2}$ are $HO$ sets in $G^{*}$ and $\Delta\nu=0$.

###### Proof.

Let $N^{*}\mathbf{p}=\mathbf{1}$. Assuming
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=0$, $\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$
or $\mathbf{x}_{A_{1}}\cdot\mathbf{p}=1$,
$\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ leads us to the contradictions as in the
proof of Proposition 2.18. Therefore, either
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ or
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$,
which, by (6), gives $N\mathbf{p}=\mathbf{1}$ or
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$, respectively.

Conversely, if $\mathbf{p}$ satisfies the conditions $N\mathbf{p}=1$ with
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ or
$N\mathbf{p}=\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ with
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$, then
in both cases $N^{*}\mathbf{p}=\mathbf{1}$ by (6).

Note that the first condition on $\mathbf{p}$ is equivalent to say that
$\mathbf{p}\in O_{1}\cap O_{2}$, where $O_{1}$ and $O_{2}$ are the sets
defined as in Lemma 2.17 with $\mathbf{c}=\mathbf{1}$. $A_{1}\cup A_{2}$ is a
$NO$ set by assumption. So if we denote the number of odd dominating patterns
of $G$ by $n$, then the number of patterns satisfying the first condition is
$n/2$ by Lemma 2.17. The second condition on $\mathbf{p}$ is equivalent to say
that $\mathbf{p}\in I_{1}\cap I_{2}$, where $I_{1}$ and $I_{2}$ are the sets
defined as in Lemma 2.17 with $\mathbf{c}=\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}$. Note that $A_{1}\cup A_{2}$ is $\overline{\mathbf{x}_{A_{1}\cup
A_{2}}}$-$NO$ by Lemma 2.6. Also, the number of the solving patterns for
$\overline{\mathbf{x}_{A_{1}\cup A_{2}}}$ is equal to number of odd dominating
patterns of $G$, which is $n$. Hence the number of patterns satisfying the
second condition is $n/2$ by Lemma 2.17. So in total, there are $n$ patterns
satisfying the first or second condition. Therefore, the number of odd
dominating patterns of $G$, which is $2^{\nu(G)}$ is equal to the number of
odd dominating patterns of $G^{*}$, which is $2^{\nu(G^{*})}$. Hence
$\Delta\nu=0$.

We see that odd dominating patterns $\mathbf{p}$ of $G^{*}$ satisfy the first
or second condition. In the first condition
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=0$ while
in the second condition
$\mathbf{x}_{A_{1}}\cdot\mathbf{p}=\mathbf{x}_{A_{2}}\cdot\mathbf{p}=1$ which
makes $A_{1}$ and $A_{2}$ $HO$ sets in $G^{*}$. ∎

We summarize the results obtained from Proposition 2.9 to 2.20 in the
following table.

Table 1.  $A_{1}$ in $G$ | $A_{2}$ in $G$ | $A_{1}$ in $G^{*}$ | $A_{2}$ in $G^{*}$ | $\Delta\nu$ | when
---|---|---|---|---|---
$A_{2}$ in $G$ |  $A_{1}\cup A_{2}$ in $G$
$NO$ | $NO$ | $NO$ | $NO$ | 0 |  $\overline{\mathbf{x}_{A_{1}}}$-$NO$ | -
$HO$ | $HO$ | 2 |  $\overline{\mathbf{x}_{A_{1}}}$-$AO$ | -
$NO$ | $AO$ | $AO$ | $HO$ | 1 |  $\overline{\mathbf{x}_{A_{1}}}$-$NO$ | -
$NO$ | $AO$ | 0 |  $\overline{\mathbf{x}_{A_{1}}}$-$AO$ | -
$AO$ | $AO$ | $AO$ | $AO$ | 0 |  $\overline{\mathbf{x}_{A_{1}}}$-$NO$ | -
$HO$ | $HO$ | 1 |  $\overline{\mathbf{x}_{A_{1}}}$-$AO$ | -
$HO$ | $HO$ | $NO$ | $NO$ | -2 | - | $HO$
$AO$ | $AO$ | -1 | - | $AO$
$HO$ | $HO$ | 0 | - | $NO$
$NO$ | $HO$ | $NO$ | $HO$ | $0$ | - | -
$AO$ | $HO$ | $NO$ | $AO$ | -1 | - | -

##  3\. Main Results

In this section we investigate the existence of edges whose addition to or
removal from a graph increases or decreases the nullity of the graph under
some specific conditions. The first natural question we ask is the following.
For a graph with positive nullity should there exist an edge whose removal
decreases the nullity of the graph? As we proved in the following theorem the
answer is affirmative.

######  Theorem 3.1.

Suppose $G$ is a graph with positive nullity. Then there exists an edge of $G$
whose removal decreases the nullity.

###### Proof.

Suppose for a contradiction that there does not exist such an edge. Since
$\nu(G)>0$, there exists a nonzero null pattern. Hence there is a half
activated vertex $u$ of $G$ (see Remark 2.4). Let $\mathbf{s}$ be an odd
dominating pattern of $G$ with $\mathbf{s}(u)=0$. For any half activated
neighbor $v$ of $u$, $\mathbf{s}(v)=0$. Otherwise the set $\\{u,v\\}$ would be
either $HO$ or $AO$, in which case the removal of the edge $uv$ decreases the
nullity by Proposition 2.18 and 2.19. On the other hand $u$ does not have any
always activated neighbor. Otherwise, removal of the edge between $u$ and that
activated vertex would decrease the nullity by Proposition 2.16. Hence
$\mathbf{s}(w)=0$ for all neighbors $w$ of $u$. Then
$\mathbf{x}_{N[u]}\cdot\mathbf{s}=0$, which contradicts with $\mathbf{s}$
being an odd dominating pattern. ∎

As a second question, we can ask the converse of the first one. For a graph
$G$ which is not complete, does there always exist a pair of non adjacent
vertices $u$ and $v$ such that the addition of the edge $uv$ to $G$ increases
the nullity? The answer is an immediate no. Because, for example, any edge
addition to the graph $K_{2}\cup K_{2}$ only decreases the nullity. But what
if the nullity of $G$ cannot decrease, i.e.; what if $G$ is always solvable?
We can see that the answer is still no by considering the cycle $C_{5}$. Cycle
$C_{5}$ is always solvable, on the other hand adding any edge to $C_{5}$ keeps
the nullity zero. Note that $C_{5}$ satisfies some special properties such as
having an odd order and being an _even graph_ i.e.; degree of all of its
vertices is even. It turns out that, if the nullity of an always solvable
graph $G$ does not increase by any edge addition then $G$ must satisfy these
two properties as we proved in Theorem 3.5. Before starting the proof we need
the following definitions and lemma.

######  Definition 3.2.

Let $G$ be a graph with vertices $u$ and $v$. If $u$ and $v$ are not adjacent
then we denote by $G+uv$ the graph obtained from $G$ by joining $u$ and $v$ by
an edge. If $u$ and $v$ are adjacent then we denote by $G-uv$ the graph
obtained from $G$ by removing the edge between $u$ and $v$.

######  Definition 3.3.

We define the _parity value_ $pr(\mathbf{x})$ of a vector
$\mathbf{x}\in\mathbb{Z}_{2}^{n}$ as
$pr(\mathbf{x}):=\mathbf{1}\cdot\mathbf{x}$.

Hence the parity value of a vector is $0$ if it has even number of nonzero
coordinates and $1$ if it has odd number of nonzero coordinates.

######  Lemma 3.4.

Let $G$ be an always solvable graph, $u$ be a vertex of $G$, $\mathbf{p}$ be
the solving pattern for $\overline{\mathbf{x}_{\\{u\\}}}$, and $\mathbf{s}$ be
the odd dominating set of $G$. Then,

(10)
$\displaystyle\overline{\mathbf{x}_{N[u]}}\cdot\mathbf{p}=\left\\{\begin{array}[]{cc}pr(\mathbf{s})&\text{if}\;\;u\;\text{is
never activated}\\\ 1-pr(\mathbf{s})&\text{if}\;\;u\;\text{is always
activated}\\\ \end{array}\right\\}.$

###### Proof.

First we take an enumeration of vertices of $G$ such that $u$ corresponds to
the first vertex. Now let $\mathbf{r}$ be the solving pattern for
$\mathbf{x}_{\\{u\\}}$. Hence, $\mathbf{r}=N^{-1}\mathbf{x}_{\\{u\\}}$ which
implies $\mathbf{r}$ is the first column vector of $N^{-1}.$ On the other
hand, $\mathbf{s}=N^{-1}\mathbf{1}$, which implies $\mathbf{s}(u)$ is equal to
the parity value of the first row vector of $N^{-1}.$ Since $N^{-1}$ is a
symmetric matrix these two observations imply $pr(\mathbf{r})=\mathbf{s}(u)$.
Furthermore, note that $\mathbf{p}=\mathbf{r}+\mathbf{s}$. Indeed,
$\mathbf{p}=N^{-1}\overline{\mathbf{x}_{\\{u\\}}}=N^{-1}(\mathbf{x}_{\\{u\\}}+\mathbf{1})=N^{-1}\mathbf{x}_{\\{u\\}}+N^{-1}\mathbf{1}=\mathbf{r}+\mathbf{s}$.
Hence
$pr(\mathbf{p})=pr(\mathbf{r})+pr(\mathbf{s})=\mathbf{s}(u)+pr(\mathbf{s}).$
So $pr(\mathbf{p})=pr(\mathbf{s})$ if $u$ is never activated and
$pr(\mathbf{p})=1+pr(\mathbf{s})=1-pr(\mathbf{s})$ if $u$ is always activated.
On the other hand,
$pr(\mathbf{p})=\mathbf{1}\cdot\mathbf{p}=\mathbf{x}_{N[u]}\cdot\mathbf{p}+\overline{\mathbf{x}_{N[u]}}\cdot\mathbf{p}=\overline{\mathbf{x}_{N[u]}}\cdot\mathbf{p}$
since
$\mathbf{x}_{N[u]}\cdot\mathbf{p}=(N\mathbf{p})(u)=\overline{\mathbf{x}_{\\{u\\}}}(u)=0.$
Hence the result follows. ∎

######  Theorem 3.5.

Suppose $G$ is an always solvable graph which is not an even graph with odd
order. Then, there exists a non-adjacent pair of vertices $u$, $v$ in $G$ such
that $G+uv$ is not always solvable.

###### Proof.

First of all note that an always solvable graph has no half activated
vertices. So all vertices are either always activated or never activated. Now
assume for a contradiction that for all non-adjacent pair of vertices $u$ and
$v$, $G+uv$ is always solvable. Since $G$ is not an even graph with odd order,
either $G$ is not an even graph or $G$ is an even graph with even order.

Assume first that $G$ is not an even graph. Then $\mathbf{1}$ cannot be the
odd dominating pattern. Hence there exists a never activated vertex $u$ of
$G$. Let $\mathbf{p}$ be the solving pattern for
$\overline{\mathbf{x}_{\\{u\\}}}$. Let $v$ be another vertex in $G$ which is
not adjacent to $u$. Since $\nu(G+uv)=\nu(G)=0$, by Proposition 2.10 and 2.11,
$\mathbf{p}(v)=\mathbf{x}_{\\{v\\}}\cdot\mathbf{p}=0$ if $v$ is never
activated and $\mathbf{p}(v)=1$ if $v$ is always activated. Hence
$\overline{\mathbf{x}_{N[u]}}\cdot\mathbf{p}$ is equal to the parity value of
the always activated vertices which are not adjacent to $u$. Note that a never
activated vertex has odd number of always activated neighbors in an always
solvable graph. Hence the parity value of the always activated vertices which
are not adjacent to $u$ is equal to $1-pr(\mathbf{s})$, where $\mathbf{s}$ is
the odd dominating pattern of $G$. On the other hand, we have
$\overline{\mathbf{x}_{N[u]}}\cdot\mathbf{p}=pr(\mathbf{s})$ by Lemma 3.4
since $u$ is a never activated vertex. So we arrive at a contradiction.

Assume second that $G$ is an even graph with even order. Then $\mathbf{1}$ is
the odd dominating pattern of $G$, in other words every vertex is always
activated. Let $\tilde{u}$ be one of these vertices. Let $\tilde{v}$ be a
vertex in $G$ which is not adjacent to $\tilde{u}$. Then, since $\tilde{v}$ is
also always activated and $\nu(G+\tilde{u}\tilde{v})=\nu(G)=0$, by Proposition
2.14, $\mathbf{\tilde{p}}(\tilde{v})=0$, where $\mathbf{\tilde{p}}$ is the
solving pattern for $\overline{\mathbf{x}_{\\{\tilde{u}\\}}}$. Hence
$\overline{\mathbf{x}_{N[\tilde{u}]}}\cdot\mathbf{\tilde{p}}=0$. However, by
Lemma 3.4,
$\overline{\mathbf{x}_{N[\tilde{u}]}}\cdot\mathbf{\tilde{p}}=1-pr(\mathbf{s})=1$
since the order of $G$ is even and every vertex is always activated. So we
arrive at a contradiction for this case as well. ∎

Note that the converse of Theorem 3.5 does not hold since the empty graph
$\overline{K_{3}}$ is an even graph with odd order but every edge addition to
it increases the nullity.

Theorem 3.1 tells us that for a graph with positive nullity, there exists an
edge whose removal decreases the nullity. However it does not tell us how much
it decreases the nullity. From Table 1 we see that nullity can decrease by $1$
or by $2$. So another natural question is that for graphs with nullity greater
than $1$ can we always find an edge whose removal decreases the nullity by
$2$. The answer of this question is negative since $K_{2}\cup K_{2}$ has
nullity $2$ but removal of any edge decreases the nullity only by $1$.
However, note that although we cannot find an edge of $K_{2}\cup K_{2}$ whose
removal decreases the nullity by $2$, there exist edges whose addition
decreases the nullity by $2$. The following theorem proves that this is not a
coincidence.

######  Theorem 3.6.

Suppose $G$ is a graph with $\nu(G)\geq 2$. Then either there exists an edge
$e$ of $G$ such that $\nu(G-e)=\nu(G)-2$ or there are non-adjacent vertices
$u$, $v$ of $G$ such that $\nu(G+uv)=\nu(G)-2$.

###### Proof.

Assume that the claim does not hold true. Then, for any pair of half activated
vertices $u$, $v$, the set $\\{u,v\\}$ is not $HO$. Otherwise, removal or
addition of the edge $uv$, depending on whether $u$ and $v$ are adjacent in
$G$ or not, would decrease the nullity by $2$ by Proposition 2.18. This is
equivalent to say that $\mathbf{x}_{\\{u,v\\}}$ is solvable. Hence
$\mathbf{x}_{\\{u,v\\}}$ is orthogonal to every null pattern by (_O 3_).

Now, assuming $\nu(G)$ is nonzero, let $\boldsymbol{\ell}$ be a nonzero null
pattern. Since $\boldsymbol{\ell}$ is nonzero there exists a half activated
vertex $u$ such that $\boldsymbol{\ell}(u)=1$ (see Remark 2.4). Let $v$ be any
half activated vertex other than $u$. Then,
$0=\mathbf{x}_{\\{u,v\\}}\cdot\boldsymbol{\ell}=\boldsymbol{\ell}(u)+\boldsymbol{\ell}(v)=1+\boldsymbol{\ell}(v)$.
Hence $\boldsymbol{\ell}(v)=1$. Moreover, $\boldsymbol{\ell}(w)=0$ for all $w$
which is either never or always activated. Otherwise $\\{w\\}$ would not be
solvable by (_O 3_). Hence $\boldsymbol{\ell}$ is the characteristic vector of
the set of half activated vertices. Since $\boldsymbol{\ell}$ was an arbitrary
nonzero null pattern, this implies $Ker(N)$ is one dimensional. So $\nu(G)=1$.
∎

Another result we have is the following.

######  Theorem 3.7.

Suppose $G$ is an always solvable graph where removal of every edge increases
the nullity. Then, every always activated vertex of $G$ has even degree and
every never activated vertex of $G$ has odd degree.

###### Proof.

Since $G$ is always solvable, all vertices are either always activated or
never activated. Let $u$ be an always activated vertex of $G$. For any never
activated neighbor $v$ of $u$, since the removal of the edge $uv$ increases
the nullity, by Proposition 2.12 and Lemma 2.8,
$\mathbf{p}(v)=\mathbf{x}_{\\{v\\}}\cdot\mathbf{p}=1$, where $\mathbf{p}$ is
the solving pattern for $\overline{\mathbf{x}_{\\{u\\}}}$. Similarly, for any
always activated neighbor $w$ of $u$, $\mathbf{p}(w)=1$ by Proposition 2.13.
Moreover, $\mathbf{p}(u)=\mathbf{x}_{\\{u\\}}\cdot\mathbf{p}=0$ by Lemma 2.6.
Consequently, $\mathbf{x}_{N[u]}\cdot\mathbf{p}=0$ if and only if the degree
of $u$ is even. On the other hand,
$\mathbf{x}_{N[u]}\cdot\mathbf{p}=(N\mathbf{p})(u)=\overline{\mathbf{x}_{\\{u\\}}}(u)=0.$
Hence degree of $u$ is even.

Let $\tilde{u}$ be a never activated vertex of $G$. For any never activated
neighbor $\tilde{v}$ of $\tilde{u}$, $\mathbf{\tilde{p}}(\tilde{v})=1$ by
Proposition 2.9, where $\mathbf{\tilde{p}}$ is the vector satisfying
$N\mathbf{\tilde{p}}=\overline{\mathbf{x}_{\\{\tilde{u}\\}}}$. On the other
hand, for any always activated neighbor $\tilde{w}$ of $\tilde{u}$,
$\mathbf{\tilde{p}}(\tilde{w})=0$ by Proposition 2.12.
$\mathbf{\tilde{p}}(\tilde{u})=\mathbf{x}_{\\{\tilde{u}\\}}\cdot\mathbf{\tilde{p}}=0$
by Lemma 2.6. Consequently, the number of never activated neighbors of
$\tilde{u}$ is even since
$\mathbf{x}_{N[\tilde{u}]}\cdot\mathbf{\tilde{p}}=0$. On the other hand, since
there is no half activated vertex, a never activated vertex has odd number of
always activated neighbors. So the degree of $\tilde{u}$, which is the sum of
never and always activated neighbors of $\tilde{u}$, is odd. ∎

We finish the set of our main results by giving a characterization of always
solvable graphs. First we need to name some types of edge additions.

######  Definition 3.8.

Let $G$ be a graph with a non-adjacent pair of vertices $u$ and $v$. Let
$\mathbf{p}$ be a solving pattern for $\overline{\mathbf{x}_{\\{u\\}}}$ in the
case $\\{u\\}$ is solvable. Then adding the edge $uv$ to $G$ is called a

_Type-1_ edge addition if $u$ is never activated, $v$ is always activated, and
$\mathbf{p}(v)=1$,

_Type-2_ edge addition if $u$ and $v$ are always activated, and
$\mathbf{p}(v)=0$,

_Type-3_ edge addition if $u$ is never activated, $v$ is always activated, and
$\mathbf{p}(v)=0$,

_Type-4_ edge addition if $u$ and $v$ are always activated, and
$\mathbf{p}(v)=1$,

_Type-5_ edge addition if $u$ is always activated, $v$ is half activated,

_Type-6_ edge addition if $u$ and $v$ are half activated, and $\\{u,v\\}$ is
half odd activated.

######  Theorem 3.9.

Suppose $G$ is a graph with $n$ edges where $n\neq 0$. Then, $G$ is always
solvable if and only if $G$ is obtained from an always solvable graph with
$n-1$ edges by a Type-1 or Type-2 edge addition or it is obtained from an
always solvable graph with $n-2$ edges by a Type-3 or a Type-4 edge addition
followed by a Type-5 or Type-6 edge addition.

###### Proof.

If $G$ is always solvable then it has no half activated vertex. On the other
hand, $G$ must have an always activated vertex $v$ with nonzero degree.
Otherwise $G$ would have a never activated vertex $w$ with no always activated
neighbors since $G$ is nonempty. But then $\mathbf{x}_{N[w]}\cdot\mathbf{s}=0$
where $\mathbf{s}$ is the odd dominating pattern of $G$, which is a
contradiction. Therefore, by Proposition 2.11-2.14, either (_Case 1_) there
exists an edge incident to $u$ whose removal keeps the nullity $0$, or (_Case
2_) removal of every edge incident to $u$ increases the nullity by $1$.

First assume that _Case 1_ holds. Then there exists a vertex $u$ adjacent to
$v$ such that $G^{\prime}:=G-uv$ is always solvable. By Proposition 2.12 and
2.13, types of activations of $u$ and $v$ in $G^{\prime}$ are equal to the
types of activations in $G$. So $u$ and $v$ is either a never activated,
always activated or always activated, always activated pair in $G^{\prime}$.
Since the nullity of $G=G^{\prime}+uv$ is the same as the nullity of
$G^{\prime}$ which is $0$, this implies $G$ is obtained from $G^{\prime}$ by a
_Type-1_ or _Type-2_ edge addition by Proposition 2.11-2.14.

Second assume that _Case 2_ holds. Then $G^{\prime}=G-uv$ has nullity $1$ for
all $u$ adjacent to $v$ in $G$. Equivalently, adding the edge $uv$ to
$G^{\prime}$ decreases the nullity by $1$. Considering all possible scenarios
stated in Proposition 2.9-2.20 (or put together in Table 1), we see that
adding the edge $uv$ to $G^{\prime}$ can decrease the nullity of $G^{\prime}$
by $1$ only under two cases which corresponds _Type-5_ and _Type-6_ edge
additions. On the other hand, since the nullity of $G^{\prime}$ is $1$, there
exists an edge $e$ of $G^{\prime}$ whose removal decreases the nullity to $0$
by Theorem 3.1. Equivalently, adding the edge $e$ to the always solvable graph
$G^{\prime\prime}:=G^{\prime}-e$ increases the nullity by $1$. Again,
considering all possible scenarios stated in Proposition 2.9-2.20, we see that
this is only possible under two cases which corresponds to _Type-3_ or
_Type-4_ edge addition.

Sufficiency part of the proof is trivial by definitions of the types of the
edge additions and by Proposition 2.11, 2.12, 2.13, 2.14, 2.16, and 2.19 ∎

## References

  * [1] A. T. Amin and P. J. Slater.  All parity realizable trees.  J. Combin. Math. Combin. Comput., 20:53–63, 1996.
  * [2] Ashok T. Amin, Lane H. Clark, and Peter J. Slater.  Parity dimension for graphs.  Discrete Math., 187(1-3):1–17, 1998.
  * [3] Ashok T. Amin, Peter J. Slater, and Guo-Hui Zhang.  Parity dimension for graphs—a linear algebraic approach.  Linear Multilinear Algebra, 50(4):327–342, 2002.
  * [4] Laura E. Ballard, Erica L. Budge, and Darin R. Stephenson.  Lights out for graphs related to one another by constructions.  Involve, 12(2):181–201, 2019.
  * [5] Ahmet Batal.  A characterization of always solvable trees in Lights Out game using the activation numbers of vertices.  arXiv e-prints, page arXiv:2008.08541, August 2020.
  * [6] Yair Caro.  Simple proofs to three parity theorems.  Ars Combin., 42:175–180, 1996.
  * [7] Robert Cowen, Stephen H. Hechler, John W. Kennedy, and Alex Ryba.  Inversion and neighborhood inversion in graphs.  Graph Theory Notes N. Y., 37:37–41, 1999.
  * [8] Stephanie Edwards, Victoria Elandt, Nicholas James, Kathryn Johnson, Zachary Mitchell, and Darin Stephenson.  Lights out on finite graphs.  Involve, 3(1):17–32, 2010.
  * [9] Henrik Eriksson, Kimmo Eriksson, and Jonas Sjöstrand.  Note on the lamp lighting problem.  volume 27, pages 357–366. 2001.  Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000).
  * [10] Alexander Giffen and Darren B. Parker.  On generalizing the “lights out” game and a generalization of parity domination.  Ars Combin., 111:273–288, 2013.
  * [11] K. Sutner.  Linear cellular automata and the Garden-of-Eden.  Math. Intelligencer, 11(2):49–53, 1989.
  * [12] Klaus Sutner.  The $\sigma$-game and cellular automata.  Amer. Math. Monthly, 97(1):24–34, 1990.