#  On $\delta$-Graphs and Delta Conjecture

Pedro Díaz Navarro Escuela de Matemática, Universidad de Costa Rica

(August, 2016)

###### Abstract

In this paper we define two infinite families of graphs called C-$\delta$
graphs and $\delta$\- graph and prove that $\delta$-graphs satisfy $\delta$
conjecture. Also we introduce a family of C-$\delta$ graphs from which we can
identify $\delta$ graphs as their complements. Finally we give a list of
C-$\delta$ graphs and the relationship with their minimum semidefinite rank.

##  1 Introduction

A graph $G$ consists of a set of vertices $V(G)=\\{1,2,\dots,n\\}$ and a set
of edges $E(G)$, where an edge is defined to be an unordered pair of vertices.
The order of $G$, denoted $|G|$, is the cardinality of $V(G)$. A graph is
simple if it has no multiple edges or loops. The complement  of a graph
$G(V,E)$ is the graph $\overline{G}=(V,\overline{E})$, where $\overline{E}$
consists of all those edges of the complete graph $K_{|G|}$ that are not in
$E$.

A matrix $A=[a_{ij}]$ is combinatorially symmetric when $a_{ij}=0$ if and only
if $a_{ji}=0$. We say that $G(A)$ is the graph of a combinatorially symmetric
matrix $A=[a_{ij}]$ if $V=\\{1,2,\dots,n\\}$ and $E=\\{\\{i,j\\}:a_{ij}\neq
0\\}$ . The main diagonal entries of $A$ play no role in determining $G$.
Define $S(G,{\mbox{\conj F}})$ as the set of all $n\times n$ matrices that are
real symmetric if ${\mbox{\conj F}}={\mbox{\conj R}}$ or complex Hermitian if
${\mbox{\conj F}}={\mbox{\conj C}}$ whose graph is $G$. The sets
$S_{+}(G,{\mbox{\conj F}})$ are the corresponding subsets of positive
semidefinite (psd) matrices. The smallest possible rank of any matrix $A\in
S(G,{\mbox{\conj F}})$ is the minimum rank of $G$, denoted
$\mathop{{\rm{mr}}}\nolimits(G,{\mbox{\conj F}})$, and the smallest possible
rank of any matrix $A\in S_{+}(G,{\mbox{\conj F}})$ is the minimum
semidefinite rank of $G$, denoted $\mathop{{\rm{mr}}}\nolimits_{+}(G)$ or
$\mathop{{\rm{msr}}}\nolimits(G)$.

In 1996, the minimum rank among real symmetric matrices with a given graph was
studied by Nylen [27]. It gave rise to the area of minimum rank problems which
led to the study of minimum rank among complex Hermitian matrices and positive
semidefinite matrices associated with a given graph. Many results can be found
for example in [1, 19, 23, 24, 27].

During the AIM workshop of 2006 in Palo Alto, CA, it was conjectured that for
any graph $G$ and infinite field $F$,
$\mathop{{\rm{mr}}}\nolimits(G,{\mbox{\conj F}})\leq|G|-\delta(G)$ where
$\delta(G)$ is the minimum degree of $G$. It was shown that for if
$\delta(G)\leq 3$ or $\delta(G)\geq|G|-2$ this inequality holds. Also it can
be verified that if $|G|\leq 6$ then
$\mathop{{\rm{mr}}}\nolimits(G,F)\leq|G|-\delta(G)$. Also it was proven that
any bipartite graph satisfies this conjecture. This conjecture is called the
Delta Conjecture. If we restrict the study to consider matrices in
$S_{+}(G,{\mbox{\conj F}})$ then delta conjecture is written as
$\mathop{{\rm{msr}}}\nolimits(G)\leq|G|-\delta(G)$. Some results on delta
conjecture can be found in [7, 13, 26, 30] but the general problem remains
unsolved.

##  2 Graph Theory Preliminaries

In this section we give definitions and results from graph theory which will
be used in the remaining chapters. Further details can be found in [8, 9, 14].

A graph $G(V,E)$ is a pair $(V(G),E(G)),$ where $V(G)$ is the set of vertices
and $E(G)$ is the set of edges together with an incidence function $\psi(G)$
that associate with each edge of $G$ an unordered pair of (not necessarily
distinct) vertices of $G$. The order of $G$, denoted $|G|$, is the number of
vertices in $G.$ A graph is said to be simple if it has no loops or multiple
edges. The complement of a graph $G(V,E)$ is the graph
$\overline{G}=(V,\overline{E}),$ where $\overline{E}$ consists of all the
edges that are not in $E$. A subgraph $H=(V(H),E(H))$ of $G=(V,E)$ is a graph
with $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G).$ An induced subgraph $H$ of
$G$, denoted G[V(H)], is a subgraph with $V(H)\subseteq V(G)$ and
$E(H)=\\{\\{i,j\\}\in E(G):i,j\in V(H)\\}$. Sometimes we denote the edge
$\\{i,j\\}$ as $ij$.

We say that two vertices of a graph $G$ are adjacent, denoted $v_{i}\sim
v_{j}$, if there is an edge $\\{v_{i},v_{j}\\}$ in $G$. Otherwise we say that
the two vertices $v_{i}$ and $v_{j}$ are non-adjacent and we denote this by
$v_{i}\not\sim v_{j}$. Let $N(v)$ denote the set of vertices that are adjacent
to the vertex $v$ and let $N[v]=\\{v\\}\cup N(v)$. The degree of a vertex $v$
in $G,$ denoted $\mathop{{\rm{d}}}\nolimits_{G}(v),$ is the cardinality of
$N(v).$ If $\mathop{{\rm{d}}}\nolimits_{G}(v)=1,$ then $v$ is said to be a
pendant vertex of $G.$ We use $\delta(G)$ to denote the minimum degree of the
vertices in $G$, whereas $\Delta(G)$ will denote the maximum degree of the
vertices in $G$.

Two graphs $G(V,E)$ and $H(V^{\prime},E^{\prime})$ are identical denoted
$G=H$, if $V=V^{\prime},E=E^{\prime}$, and $\psi_{G}=\psi_{H}$ . Two graphs
$G(V,E)$ and $H(V^{\prime},E^{\prime})$ are isomorphic, denoted by $G\cong H$,
if there exist bijections $\theta:V\to V^{\prime}$ and $\phi:E\to E^{\prime}$
such that $\psi_{G}(e)=\\{u,v\\}$ if and only if
$\psi_{H}(\phi(e))=\\{\theta(u),\theta(v)\\}$.

A complete graph is a simple graph in which the vertices are pairwise
adjacent. We will use $nG$ to denote $n$ copies of a graph $G$. For example,
$3K_{1}$ denotes three isolated vertices $K_{1}$ while $2K_{2}$ is the graph
given by two disconnected copies of $K_{2}$.

A path is a list of distinct vertices in which successive vertices are
connected by edges. A path on $n$ vertices is denoted by $P_{n}.$ A graph $G$
is said to be connected if there is a path between any two vertices of $G$. A
cycle on $n$ vertices, denoted $C_{n},$ is a path such that the beginning
vertex and the end vertex are the same. A tree is a connected graph with no
cycles. A graph $G(V,E)$ is said to be chordal if it has no induced cycles
$C_{n}$ with $n\geq 4$. A component of a graph $G(V,E)$ is a maximal connected
subgraph. A cut vertex is a vertex whose deletion increases the number of
components.

The union $G\cup G_{2}$ of two graphs $G_{1}(V_{1},E_{1})$ and
$G_{2}(V_{2},G_{2})$ is the union of their vertex set and edge set, that is
$G\cup G_{2}(V_{1}\cup V_{2},E_{1}\cup E_{2}$. When $V_{1}$ and $V_{2}$ are
disjoint their union is called disjoint union and denoted $G_{1}\sqcup G_{2}$.

##  3 The Minimum Semidefinite Rank of a Graph

In this section we will establish some of the results for the minimum
semidefinite rank ($\mathop{{\rm{msr}}}\nolimits$)of a graph $G$ that we will
be using in the subsequent chapters.

A positive definite matrix $A$ is an Hermitian $n\times n$ matrix such that
$x^{\star}Ax>0$ for all nonzero $x\in{\mbox{\conj C}}^{n}$. Equivalently, $A$
is a $n\times n$ Hermitian positive definite matrix if and only if all the
eigenvalues of $A$ are positive ([20], p.250).

A $n\times n$ Hermitian matrix $A$ such that $x^{\star}Ax\geq 0$ for all
$x\in{\mbox{\conj C}}^{n}$ is said to be positive semidefinite (psd).
Equivalently, $A$ is a $n\times n$ Hemitian positive semidefinite matrix if
and only if $A$ has all eigenvalues nonnegative ([20], p.182).

If
$\overrightarrow{V}=\\{\overrightarrow{v_{1}},\overrightarrow{v_{2}},\dots,\overrightarrow{v_{n}}\\}\subset{\mbox{\conj
R}}^{m}$ is a set of column vectors then the matrix $A^{T}A$, where
$A=\left[\begin{array}[]{cccc}\overrightarrow{v_{1}}&\overrightarrow{v_{2}}&\dots&\overrightarrow{v_{n}}\end{array}\right]$
and $A^{T}$ represents the transpose matrix of $A$, is a psd matrix called the
Gram matrix of $\overrightarrow{V}$. Let $G(V,E)$ be a graph associated with
this Gram matrix. Then $V_{G}=\\{v_{1},\dots,v_{n}\\}$ correspond to the set
of vectors in $\overrightarrow{V}$ and E(G) correspond to the nonzero inner
products among the vectors in $\overrightarrow{V}$. In this case
$\overrightarrow{V}$ is called an orthogonal representation of $G(V,E)$ in
${\mbox{\conj R}}^{m}$. If such an orthogonal representation exists for $G$
then $\mathop{{\rm{msr}}}\nolimits(G)\leq m$.

The maximum positive semidefinite nullity  of a graph $G$, denoted $M_{+}(G)$
is defined by
$M_{+}(G)=\mathop{{\rm{max}}}\nolimits\\{\mathop{{\rm{null}}}\nolimits(A):A\
\hbox{ is symmetric and positive semidefinite and }\ G(A)=G\\}$, where $G(A)$
is the graph obtained from the matrix $A$. From the rank-nullity theorem we
get $\mathop{{\rm{msr}}}\nolimits(G)+M_{+}(G)=|G|$.

Some of the most common results about the minimum semidefinite rank of a graph
are the following:

######  Result 3.1.

[19] If $T$ is a tree then $\mathop{{\rm{msr}}}\nolimits(T)=|T|-1$.

######  Result 3.2.

[11] The cycle $C_{n}$ has minimum semidefinite rank $n-2$.

######  Result 3.3.

[11] If a connected graph $G$ has a pendant vertex $v$, then
$\mathop{{\rm{msr}}}\nolimits(G)=\mathop{{\rm{msr}}}\nolimits(G-v)+1$ where
$G-v$ is obtained as an induced subgraph of $G$ by deleting $v$.

######  Result 3.4.

[18] If $G$ is a connected, chordal graph, then
$\mathop{{\rm{msr}}}\nolimits(G)=\mathop{{\rm{cc}}}\nolimits(G).$

######  Result 3.5.

[10] If a graph $G(V,E)$ has a cut vertex, so that $G=G_{1}\cdot G_{2}$, then
$\mathop{{\rm{msr}}}\nolimits(G)=\mathop{{\rm{msr}}}\nolimits(G_{1})+\mathop{{\rm{msr}}}\nolimits(G_{2})$.

##  4 $\mathbf{\delta}$-Graphs and the Delta Conjecture

In this section we define a new family of graphs called $\delta$-graphs and
show that they satisfy the delta conjecture.

######  Definition 4.1.

Suppose that $G=(V,E)$ with $|G|=n\geq 4$ is simple and connected such that
$\overline{G}=(V,\overline{E})$ is also simple and connected. We say that $G$
is a $\mathbf{\delta}$-graph if we can label the vertices of $G$ in such a way
that

  1. (1)

the induced graph of the vertices $v_{1},v_{2},v_{3}$ in $G$ is either
$3K_{1}$ or $K_{2}\sqcup K_{1}$, and

  2. (2)

for $m\geq 4$, the vertex $v_{m}$ is adjacent to all the prior vertices
$v_{1},v_{2},\dots,v_{m-1}$ except for at most
$\displaystyle{\left\lfloor\frac{m}{2}-1\right\rfloor}$ vertices.

######  Definition 4.2.

Suppose that a graph $G(V,E)$ with $|G|=n\geq 4$ is simple and connected such
that $\overline{G}=(V,\overline{E})$ is also simple and connected. We say that
$G(V,E)$ is a C-$\mathbf{\delta}$ graph if $\overline{G}$ is a $\delta$-graph.

In other words, $G$ is a C-$\mathbf{\delta}$ graph if we can label the
vertices of $G$ in such a way that

  1. (1)

the induced graph of the vertices $v_{1},v_{2},v_{3}$ in $G$ is either $K_{3}$
or $P_{3}$, and

  2. (2)

for $m\geq 4$, the vertex $v_{m}$ is adjacent to at most
$\displaystyle{\left\lfloor\frac{m}{2}-1\right\rfloor}$ of the prior vertices
$v_{1},v_{2},\dots,v_{m-1}$.

######  Example 4.3.

The cycle $C_{n},n\geq 6$ is a C-$\delta$ graph and its complement is a
$\delta$-graph.

Figure 1: The Graphs $C_{6}$ and the 3-Prism

Note that we can label the vertices of $C_{6}$ clockwise
$v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}$. The graph induced by
$v_{1},v_{2},v_{3}$ is $P_{3}$. The vertex $v_{4}$ is adjacent to a prior
vertex which is $v_{3}$. Also, the vertex $v_{5}$ is adjacent to vertex
$v_{4}$ and the vertex $v_{6}$ is adjacent to two prior vertices $v_{1}$ and
$v_{5}$. Hence, $C_{6}$ is C-$\delta$ graph. The $3$-prism which is isomorphic
to the complement of $C_{6}$, is a $\delta$-graph.

######  Lemma 4.4.

Let $G(V,E)$ be a $\delta$-graph. Then the induced graph of
$\\{v_{1},v_{2},v_{3}\\}$ in $G$ denoted by $H$ has an orthogonal
representation in ${\mbox{\conj R}}^{\Delta(\overline{G})+1}$ satisfying the
following conditions:

  1. (i)

the vectors in the orthogonal representation of $H$ can be chosen with nonzero
coordinates, and

  2. (ii)

$\overrightarrow{v}\not\in\mathop{{\rm{Span}}}\nolimits(\overrightarrow{u})$
for each pair of distinct vertices $u,v$ in $H$.

PROOF.Let $G(V,E)$ be a $\delta$-graph. Label the vertices of $G$ in such a
way that the labeling satisfies the conditions (1) and (2) for
$\delta$-graphs. Let $H$ be the induced graph in $G$ of
$\\{v_{1},v_{2},v_{3}\\}\subseteq V$. Then $H$ is either $3K_{1}$ or
$K_{2}\sqcup K_{1}$. Since $G$ and $\overline{G}$ are simple and connected it
follows that

$2\leq\Delta(\overline{G})\leq n-2$

Let $\\{\overrightarrow{e}_{j}\\},j=1,2,\dots,\Delta(\overline{G})+1$ be the
standard orthonormal basis for ${\mbox{\conj R}}^{\Delta(\overline{G})+1}$.
Case 1. Suppose the induced graph $H$ of $\\{v_{1},v_{2},v_{3}\\}\subseteq V$
in $G$ is $3K_{1}$ which is disconnected. Choose
$\overrightarrow{v_{1}},\overrightarrow{v_{2}},\overrightarrow{v_{3}}$ in
${\mbox{\conj R}}^{\Delta(\overline{G})+1}$ corresponding to
$v_{1},v_{2},v_{3}$ respectively such that:

$\displaystyle\overrightarrow{v_{1}}$ $\displaystyle=$
$\displaystyle\displaystyle{\sum_{j=1}^{\Delta(\overline{G})+1}k_{1,j}\overrightarrow{e}_{j}}$
$\displaystyle\overrightarrow{v_{2}}$ $\displaystyle=$
$\displaystyle\displaystyle{\sum_{j=1}^{\Delta(\overline{G})+1}k_{2,j}\overrightarrow{e}_{j}}$
$\displaystyle\overrightarrow{v_{3}}$ $\displaystyle=$
$\displaystyle\displaystyle{\sum_{j=1}^{\Delta(\overline{G})+1}k_{3,j}\overrightarrow{e}_{j}}$

where the scalars $k_{1,j},j=1,2,\dots,\Delta(\overline{G})+1$, and
$k_{2,s},s=1,2,\dots,\Delta(\overline{G})$ are chosen not zero from different
field extensions in the following way:

  * $k_{1,1}\not\in{\mbox{\conj Q}}$,

  * $k_{1,2}\not\in{\mbox{\conj Q}}[k_{1,1}]$,

  * $k_{1,3}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2}]$,

  * $\vdots$

  * $k_{1,\Delta(\overline{G})+1}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},\dots,k_{1,\Delta(\overline{G})}]$,

  * $k_{2,1}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},\dots,k_{1,\Delta(\overline{G})+1}]$,

  * $k_{2,2}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1}]$,

  * $\vdots$

  * $k_{2,\Delta(\overline{G})}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})-1}]$.

Now choose

$k_{2,\Delta(\overline{G})+1}=\frac{-1}{k_{1,\Delta(\overline{G})+1}}\displaystyle{\sum_{j=1}^{\Delta(\overline{G})}k_{1,j}k_{2,j}}$

As a consequence
$\langle\overrightarrow{v}_{1},\overrightarrow{v}_{2}\rangle=0$.

In order to find a vector $\overrightarrow{v}_{3}$, we need to solve the
$2\times(\Delta(\overline{G})+1)$ system satisfying

$\displaystyle\langle\overrightarrow{v}_{1},\overrightarrow{v}_{3}\rangle$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle\langle\overrightarrow{v}_{2},\overrightarrow{v}_{3}\rangle$
$\displaystyle=$ $\displaystyle 0$

in the variables $k_{3,j},j=1,2,\dots,\Delta(\overline{G})+1$. The homogeneous
system has infinitely many solutions because $\Delta(\overline{G})+1\geq 3$.
Reducing the matrix of this system to echelon form we get

$\left(\begin{array}[]{ccccccc}k_{1,1}&k_{1,2}&k_{1,3}&\dots&k_{1,\Delta(\overline{G})+1}\\\
k_{2,1}&k_{2,2}&k_{2,3}&\dots&k_{2,\Delta(\overline{G})+1}\\\
\end{array}\right)\sim$
$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}\\\
k_{2,1}&k_{2,2}&k_{2,3}&\dots&k_{2,\Delta(\overline{G})+1}\\\
\end{array}\right)\sim$

$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}\\\
0&k_{2,2}-\frac{k_{2,1}k_{1,2}}{k_{1,1}}&k_{2,3}-\frac{k_{2,1}k_{1,3}}{k_{1,1}}&\dots&k_{2,\Delta(\overline{G})+1}-\frac{k_{2,1}k_{1,\Delta(\overline{G})+1}}{k_{1,1}}\\\
\end{array}\right)$

Let $\alpha=k_{2,2}-\frac{k_{2,1}k_{1,2}}{k_{1,1}}$. Since $\alpha\neq 0$
because $k_{2,2}\not\in{\mbox{\conj
Q}}[k_{1,1},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1}]$. We can get the
echelon form of the matrix by multiplying the second row by
$\frac{1}{\alpha}$.

$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}\\\
0&1&\frac{1}{\alpha}(k_{2,3}-\frac{k_{2,1}k_{1,3}}{k_{1,1}})&\dots&\frac{1}{\alpha}(k_{2,\Delta(\overline{G})+1}-\frac{k_{2,1}k_{1,\Delta(\overline{G})+1}}{k_{1,1}})\\\
\end{array}\right)$

Since the system has infinitely many solutions,
$k_{3,j},j=3,\dots,\Delta(\overline{G})+1$ are free parameters. We can choose
them from different field extensions in the following way,

  * $k_{3,3}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})+1}]$,

  * $k_{3,4}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})+1},k_{3,1}]$,

  * $\vdots$

  * $k_{3,\Delta(\overline{G})+1}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})+1},k_{3,3},\dots,k_{3,\Delta(\overline{G})}]$.

Since $k_{2,j}-\frac{k_{2,1}k_{1,j}}{k_{1,1}}\neq
0,j=3,\dots,\Delta(\overline{G})+1$, we can choose these parameters such that
$k_{3,1}$ and $k_{3,2}$ are also nonzero. Therefore we get
$\langle\overrightarrow{v}_{1},\overrightarrow{v}_{3}\rangle=\langle\overrightarrow{v}_{2},\overrightarrow{v}_{3}\rangle=0$.
As a result
$\overrightarrow{v_{1}},\overrightarrow{v_{2}},\overrightarrow{v_{3}}$ is an
orthogonal representation of the induced graph $H=3K_{1}$ satisfying
conditions (i) and (ii).
Case 2. Suppose the induced graph $H$ is $K_{2}\sqcup K_{1}$. Let us assume
$v_{1}\not\sim v_{2},v_{2}\not\sim v_{3}$, and $v_{1}\sim v_{3}$.
The vectors $\overrightarrow{v}_{1}$ and $\overrightarrow{v}_{2}$ for the
vertices $v_{1}$ and $v_{2}$ respectively can be chosen in the same way as in
case 1 to get $\langle\overrightarrow{v}_{1},\overrightarrow{v}_{2}\rangle=0$.
In order to find a vector
$\overrightarrow{v_{3}}=k_{3,1}\overrightarrow{e_{1}}+k_{3,2}\overrightarrow{e_{2}}+\dots+k_{3,\Delta(\overline{G})+1}\overrightarrow{e}_{\Delta(\overline{G})+1}\in{\mbox{\conj
R}}^{\Delta(\overline{G})+1}$ with nonzero components for the vertex $v_{3}$
we know that the vector $\overrightarrow{v}_{3}$ should satisfy the system

$\displaystyle\langle\overrightarrow{v_{1}},\overrightarrow{v_{3}}\rangle$
$\displaystyle=$ $\displaystyle g_{1},\ \ g_{1}\neq 0$
$\displaystyle\langle\overrightarrow{v_{2}},\overrightarrow{v_{3}}\rangle$
$\displaystyle=$ $\displaystyle 0$

in the variables $k_{3,j},j=1,2,\dots,\Delta(\overline{G})+1$ because
$v_{1}\sim v_{3}$ and $v_{2}\not\sim v_{3}$ in $G$. Therefore, rewriting the
system in the form

$\displaystyle
k_{1,1}k_{3,1}+k_{1,2}k_{3,2}+\dots+k_{1,\Delta(\overline{G})+1}k_{3,\Delta(\overline{G})+1}$
$\displaystyle=g_{1},$ (1) $\displaystyle
k_{2,1}k_{3,1}+k_{2,2}k_{3,2}+\dots+k_{2,\Delta(\overline{G})+1}k_{3,\Delta(\overline{G})+1}$
$\displaystyle=0$ (2)

the augmented matrix of the non-homogeneous system becomes

$\left(\begin{array}[]{ccccccc}k_{1,1}&k_{1,2}&k_{1,3}&\dots&k_{1,\Delta(\overline{G})+1}&|&g_{1}\\\
k_{2,1}&k_{2,2}&k_{2,3}&\dots&k_{2,\Delta(\overline{G})+1}&|&0\\\
\end{array}\right)$

Since $\Delta(\overline{G})+1\geq 3$, the system has infinitely many solutions
depending on one or more free parameters if the system is consistent. Since
$k_{1,1}$ is nonzero, we can divide the first row by $k_{1,1}$ to obtain

$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&|&\frac{g_{1}}{k_{1,1}}\\\
k_{2,1}&k_{2,2}&k_{2,3}&\dots&k_{2,\Delta(\overline{G})+1}&|&0\\\
\end{array}\right)\sim$
$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&|&\frac{g_{1}}{k_{1,1}}\\\
0&k_{2,2}-\frac{k_{1,2}k_{2,1}}{k_{1,1}}&k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}}&\dots&k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}}&|&-\frac{g_{1}k_{2,1}}{k_{1,1}}\\\
\end{array}\right)$

and since $k_{2,2}\not\in{\mbox{\conj Q}}[k_{1,2},k_{2,1},k_{1,1}]$,
$k_{2,2}-\frac{k_{1,2}k_{2,1}}{k_{1,1}}\neq 0$. Hence we obtain the echelon
form of the matrix dividing by $\alpha=k_{2,2}-\frac{k_{1,2}k_{2,1}}{k_{1,1}}$

$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&|&\frac{g_{1}}{k_{1,1}}\\\
0&1&\frac{1}{\alpha}(k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}})&\dots&\frac{1}{\alpha}(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}})&|&-\frac{g_{1}k_{2,1}}{\alpha
k_{1,1}}\\\ \end{array}\right)$

Choose $k_{3,3}\neq 0,k_{3,4}\neq 0,\dots,k_{3,\Delta(\overline{G})+1}\neq 0$
one by one from different field extensions ${\mbox{\conj
Q}}[\gamma_{3}],\dots,\\\ {\mbox{\conj Q}}[\gamma_{\Delta(\overline{G})+1}]$
such that ${\mbox{\conj Q}}[\gamma_{i}],i=3,\dots,\Delta(\overline{G})+1$ is
not a field extension in the lattice $L(k_{1,1},\dots,\\\
k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})+1},\gamma_{3},\gamma_{4},\dots,\gamma_{i-1})$.
Therefore, since $g_{1}$ is nonzero, we can choose $g_{1}\in{\mbox{\conj R}}$
in such a way that $g_{1}$ does not belong to any of the prior field
extensions used so far and satisfy

$\displaystyle\frac{-g_{1}k_{2,1}}{\alpha
k_{1,1}}-\frac{1}{\alpha}\left((k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}})k_{3,3}+\dots+(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}})k_{3,\Delta(\overline{G})+1}\right)$
$\displaystyle\neq$ $\displaystyle 0\ \ $

which implies

$\displaystyle g_{1}$ $\displaystyle\neq$
$\displaystyle\frac{-k_{1,1}}{k_{2,1}}\left((k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}})k_{3,2}+\dots+(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}})k_{3,\Delta(\overline{G})+1}\right).$
(3)

Also

$\displaystyle\frac{g_{1}}{k_{1,1}}-\left(\frac{k_{1,2}}{k_{1,1}}k_{3,2}+\frac{k_{1,3}}{k_{1,1}}k_{3,3}+\dots+\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}k_{3,\Delta(\overline{G})+1}\right)$
$\displaystyle\neq$ $\displaystyle 0$

which implies

$\displaystyle g_{1}$ $\displaystyle\neq$ $\displaystyle
k_{1,1}\left(\frac{k_{1,2}}{k_{1,1}}k_{3,2}+\frac{k_{1,3}}{k_{1,1}}k_{3,3}+\dots+\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}k_{3,\Delta(\overline{G})+1}\right).$
(4)

Thus, choosing $g_{1}\neq 0$ satisfying 3 and 4 we get that the system 1 and 2
is consistent and at least one of its solutions satisfies the adjacency
condition and the orthogonal condition for $\overrightarrow{v}_{3}$ such that
none of the coordinates of the vectors
$\overrightarrow{v_{1}},\overrightarrow{v_{2}},\overrightarrow{v_{3}}\in{\mbox{\conj
R}}^{\Delta(\overline{G})+1}$ are zero. Therefore
$\\{\overrightarrow{v}_{1},\overrightarrow{v}_{2},\overrightarrow{v}_{3}\\}$
is an orthogonal representation in ${\mbox{\conj R}}^{\Delta(\overline{G})+1}$
for the induced graph $H=K_{2}\sqcup K_{1}$ satisfying condition (i). Note
that if $\overrightarrow{v}_{3}=a\overrightarrow{v}_{1},a\in{\mbox{\conj R}}$
then $k_{3,1}=ak_{1,1}$ and
$k_{3,\Delta(\overline{G})+1}=ak_{1,\Delta(\overline{G})+1}$ which implies
that $a=\frac{k_{3,1}}{k_{1,1}}$ and
$a=\frac{k_{3,\Delta(\overline{G})+1}}{k_{1,\Delta(\overline{G})+1}}$. As a
consequence
$k_{3,\Delta(\overline{G})+1}=\frac{k_{3,1}}{k_{1,1}}k_{1,\Delta(\overline{G})+1}$.
Hence $k_{3,\Delta(\overline{G})+1}\in{\mbox{\conj
Q}}[k_{1,1},k_{3,1},k_{1,\Delta(\overline{G})+1}]$ which is a contradiction
because $k_{3,\Delta(\overline{G})+1}$ was chosen from a different field
extension. Hence, $\overrightarrow{v}_{3}$ and $\overrightarrow{v}_{1}$ are
linearly independent and the vectors
$\overrightarrow{v}_{1},\overrightarrow{v}_{2},\overrightarrow{v}_{3}$ are
pairwise linearly independent satisfying condition (ii). $\Box$

######  Theorem 4.5.

Let $G(V,E)$ be a $\delta$-graph then

$\mathop{{\rm{msr}}}\nolimits(G)\leq\Delta(\overline{G})+1=|G|-\delta(G)$

PROOF. Let $G(V,E)$ be a $\delta$ graph. Let
$Y_{3}(\\{v_{1},v_{2},v_{3}\\},E_{Y_{3}})$ be the graph induced by the
vertices $v_{1},v_{2}$, and $v_{3}$ which is either $3K_{1}$ or $K_{2}\sqcup
K_{1}$. By Lemma 4.4, $Y_{3}$ has an orthogonal representation in
${\mbox{\conj R}}^{\Delta(\overline{G})+1}$. Also, from Lemma 4.4 we have

  1. (1)

The components of vectors in the orthogonal representation of $Y_{3}$ are all
nonzero.

  2. (2)

$\overrightarrow{v}\not\in\mathop{{\rm{Span}}}\nolimits(\overrightarrow{u})$
for each pair of distinct vertices $u,v$ in $V_{Y_{3}}$.

From the definition of $\delta$-graph we have

  1. (3)

$G(V,E)$ can be constructed starting with $Y_{3}(V_{Y_{3}},E_{Y_{3}})$ and
adding one vertex at a time such that the newly added vertex $v_{m},m\geq 4$
is adjacent to all prior vertices $v_{1},v_{2},\dots,v_{m-1}$ except for at
most $\displaystyle{\left\lfloor\frac{m}{2}-1\right\rfloor}$ vertices.

Applying condition (3) we get a sequence of subgraphs
$Y_{3},Y_{4},\dots,Y_{m},\dots,Y_{|G|}$ in $G$ induced by
$\\{v_{1},v_{2},v_{3}\\},\\{v_{1},v_{2},v_{3},v_{4}\\},\dots,\\{v_{1},v_{2},v_{3},v_{4},\dots,v_{m}\\},$
$\dots,\\{v_{1},v_{2},v_{3},v_{4},\dots,v_{|G|}\\}$ respectively.

We will prove that $Y_{j}=(V_{j},E_{j})$ has an orthogonal representation in
${\mbox{\conj R}}^{\Delta(\overline{G})+1}$ for all $j=3,4,\dots,|G|$,
satisfying conditions (1) and (2) above. For that purpose, consider the
orthogonal representation of $Y_{3}$ satisfying conditions (i) and (ii) given
by Lemma 4.4.

$\displaystyle\overrightarrow{v_{1}}$ $\displaystyle=$ $\displaystyle
k_{1,1}\overrightarrow{e_{1}}+k_{1,2}\overrightarrow{e_{2}}+\dots+k_{1,\Delta(\overline{G})+1}\overrightarrow{e}_{\Delta(\overline{G})+1}$
$\displaystyle\overrightarrow{v_{2}}$ $\displaystyle=$ $\displaystyle
k_{2,1}\overrightarrow{e_{1}}+k_{2,2}\overrightarrow{e_{2}}+\dots+k_{2,\Delta(\overline{G})+1}\overrightarrow{e}_{\Delta(\overline{G})+1}$
$\displaystyle\overrightarrow{v_{3}}$ $\displaystyle=$ $\displaystyle
k_{3,1}\overrightarrow{e_{1}}+k_{3,2}\overrightarrow{e_{2}}+\dots+k_{3,\Delta(\overline{G})+1}\overrightarrow{e}_{\Delta(\overline{G})+1}$

where all $k_{i,j},j=1,2,\dots,\Delta(\overline{G})+1,i=1,2,3$, are nonzero
and are chosen from different field extensions as in the proof of Lemma 4.4.
Let $v_{4}$ be a vertex of $G$ such that $v_{4}$ is adjacent to all of
$v_{1},v_{2},v_{3}$ except at most $\left\lfloor\frac{4}{2}-1\right\rfloor=1$
vertex. Since $G$ and $\overline{G}$ are simple and connected
$2\leq\Delta(\overline{G})$ and therefore $\Delta(\overline{G})+1\geq 3$.

######  CLAIM 4.6.

$Y_{4}$ induced by $\\{v_{1},v_{2},v_{3},v_{4}\\}$ has an orthogonal
representation in ${\mbox{\conj R}}^{\Delta(\overline{G})+1}$ satisfying
conditions (1) and (2) above.

PROOF OF CLAIM.We know that

$d_{\overline{G}}(v_{4})\leq\Delta(\overline{G})<\Delta(\overline{G})+1$

Since $V_{Y_{3}}=\\{v_{1},v_{2},v_{3}\\}$ from Lemma 4.4 we have an orthogonal
representation for the induced subgraph of $V_{Y_{3}}$ of $G$ in ${\mbox{\conj
R}}^{\Delta(\overline{G})+1}$ satisfying conditions (1) and (2). We need to
find a vector $\overrightarrow{v_{4}}$ for the vertex $v_{4}$ where

$\overrightarrow{v_{4}}=k_{4,1}\overrightarrow{e_{1}}+k_{4,2}\overrightarrow{e_{2}}+\dots+k_{4,\Delta(\overline{G})+1}\overrightarrow{e}_{\Delta(\overline{G})+1}$

satisfying conditions (1) and (2). Since $v_{4}$ is adjacent with all prior
vertices except for at most one of them we have four cases:

  1. 1.

$v_{4}$ is adjacent to $v_{1},v_{2}$ and $v_{3}$ in $G$.

  2. 2.

$v_{4}$ is adjacent to only $v_{1}$ and $v_{2}$ in $G$.

  3. 3.

$v_{4}$ is adjacent to only $v_{1}$ and $v_{3}$ in $G$.

  4. 4.

$v_{4}$ is adjacent to only $v_{2}$ and $v_{3}$ in $G$.

Case 1. $v_{4}\sim v_{1},v_{4}\sim v_{2},v_{4}\sim v_{3}$ in $G$.
Choose $k_{4,j},j=1,\dots,\Delta(\overline{G})+1$ as follows:

  1. $k_{4,1}=\gamma_{4,1}$ does not belong to any of the field extensions in the lattice of fields $L[{\mbox{\conj Q}}[k_{i,j}]],\\\ i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$ .

  2. $k_{4,2}=\gamma_{4,2}$ does not belong to any of the field extensions in the lattice of field extensions $L[{\mbox{\conj Q}}[k_{i,j},\gamma_{4,1}],i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$.

  3. $k_{4,3}=\gamma_{4,3}$ does not belong to any of the field extensions in the lattice of field extensions $L[{\mbox{\conj Q}}[k_{i,j},\gamma_{4,1},\gamma_{4,2}]],i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$.

  4. Continuing the process until $k_{4,\Delta(\overline{G})+1}$ to obtain

  5. $k_{4,\Delta(\overline{G})+1}=\gamma_{4,\Delta(\overline{G})+1}$ does not belong to any of the field extensions in the lattice of field extensions $L[{\mbox{\conj Q}}[k_{i,j},\gamma_{4,1},\gamma_{4,2},\dots,\gamma_{4,\Delta(\overline{G})}]],i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$.

Then $k_{4,j}\neq 0$ for all $j=1,2,\dots,\Delta(\overline{G})+1$ and
$\overrightarrow{v_{4}}\not\in\mathop{{\rm{Span}}}\nolimits(\overrightarrow{v_{i}}),i=1,2,3$.
As a consequence
$\\{\overrightarrow{v_{1}},\overrightarrow{v_{2}},\overrightarrow{v_{3}},\overrightarrow{v_{4}}\\}$
is an orthogonal representation of $Y_{4}$ at ${\mbox{\conj
R}}^{\Delta(\overline{G})+1}$. Note that if
$\langle\overrightarrow{v}_{4},\overrightarrow{v}_{1}\rangle=0$ then we can
solve this equation for $k_{4,\Delta(\overline{G})+1}$ which implies that
$k_{4,\Delta(\overline{G})+1}\in L[{\mbox{\conj
Q}}[k_{i,j},\gamma_{4,1},\gamma_{4,2},\dots,\\\
\gamma_{4,\Delta(\overline{G})}]],i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$
which is a contradiction. Therefore,
$\langle\overrightarrow{v}_{4},\overrightarrow{v}_{1}\rangle\neq 0$. In the
same way we can prove that
$\langle\overrightarrow{v}_{4},\overrightarrow{v}_{2}\rangle\neq 0$ and
$\langle\overrightarrow{v}_{4},\overrightarrow{v}_{3}\rangle\neq 0$.

Case 2. $v_{4}\sim v_{1},v_{4}\sim v_{2},v_{4}\not\sim v_{3}$ in $G$.

Since $v_{4}\sim v_{1}$ and $v_{4}\sim v_{2}$ and $v_{4}\not\sim v_{3}$ then

$\displaystyle\langle\overrightarrow{v_{4}},\overrightarrow{v_{1}}\rangle$
$\displaystyle=$ $\displaystyle g_{4,1},\ g_{4,1}\neq 0$
$\displaystyle\langle\overrightarrow{v_{4}},\overrightarrow{v_{2}}\rangle$
$\displaystyle=$ $\displaystyle g_{4,2},\ g_{4,2}\neq 0$
$\displaystyle\langle\overrightarrow{v_{4}},\overrightarrow{v_{3}}\rangle$
$\displaystyle=$ $\displaystyle 0.$

From these conditions the system $S$ in the variables
$k_{4,j},j=1,2,\dots,\Delta(\overline{G})+1$ becomes,

$\displaystyle
k_{1,1}k_{4,1}+k_{1,2}k_{4,2}+\dots+k_{1,\Delta(\overline{G})+1}k_{4,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle g_{4,1},g_{4,1}\neq 0$ $\displaystyle
k_{2,1}k_{4,1}+k_{2,2}k_{4,2}+\dots+k_{2,\Delta(\overline{G})+1}k_{4,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle g_{4,2},g_{4,2}\neq 0$ $\displaystyle
k_{3,1}k_{4,1}+k_{3,2}k_{4,2}+\dots+k_{3,\Delta(\overline{G})+1}k_{4,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle 0$

where $k_{i,j},i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$ were chosen from
different field extensions as in the proof of Lemma 4.4. Since

$d_{\overline{G}}(v_{4})\leq\Delta(\overline{G})<\Delta(\overline{G})+1$

in $\overline{G}$, the number of equations from the orthogonal conditions in
the systems are at most $\Delta(\overline{G})<\Delta(\overline{G})+1$, which
means that if the non-homogeneous system is consistent then the system will
have infinitely many solutions because the system will have at least one free
variable. The augmented matrix of the system becomes

$\left(\begin{array}[]{cccccc}k_{1,1}&k_{1,2}&\dots&k_{1,\Delta(\overline{G})+1}&|&g_{4,1}\\\
k_{2,1}&k_{2,2}&\dots&k_{2,\Delta(\overline{G})+1}&|&g_{4,2}\\\
k_{3,1}&k_{3,2}&\dots&k_{3,\Delta(\overline{G})+1}&|&0\end{array}\right)$

where $g_{4,1}\neq 0,g_{4,2}\neq 0$ are nonzero real numbers.

In order to guarantee that all adjacency conditions are satisfied consider the
matrix $3\times(\Delta(\overline{G})+3)$ below in the variables
$k_{4,1},k_{4,2},\dots,k_{4,\Delta(\overline{G})+1},-g_{4,1},-g_{4,2}$. It is
possible to consider $-g_{4,1}$ and $-g_{4,2}$ as variables because we only
need them to be nonzero. So we can consider them as two additional variables
of the homogeneous system $S_{H}$ which has the following augmented matrix:

$\left(\begin{array}[]{cccccc}k_{1,1}&k_{1,2}&\dots&k_{1,\Delta(\overline{G})+1}&1&0\\\
k_{2,1}&k_{2,2}&\dots&k_{2,\Delta(\overline{G})+1}&0&1\\\
k_{3,1}&k_{3,2}&\dots&k_{3,\Delta(\overline{G})+1}&0&0\end{array}\right).$

Multiplying the first row by $\frac{1}{k_{1,1}},k_{1,1}\neq 0$ we get

$\left(\begin{array}[]{cccccc}1&\frac{k_{1,2}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&\frac{1}{k_{1,1}}&0\\\
k_{2,1}&k_{2,2}&\dots&k_{2,\Delta(\overline{G})+1}&0&1\\\
k_{3,1}&k_{3,2}&\dots&k_{3,\Delta(\overline{G})+1}&0&0\end{array}\right).$

Multiplying the first row by $-k_{2,1}$ and adding the result to the second
row and multiplying the first row by $-k_{3,1}$ and adding to the third row we
get

$\left(\begin{array}[]{cccccc}1&\frac{k_{1,2}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&\frac{1}{k_{1,1}}&0\\\
0&k_{2,2}-\frac{k_{1,2}k_{2,1}}{k_{1,1}}&\dots&k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}}&-\frac{k_{2,1}}{k_{1,1}}&1\\\
0&k_{3,2}-\frac{k_{1,2}k_{3,1}}{k_{1,1}}&\dots&k_{3,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{3,1}}{k_{1,1}}&0&0\end{array}\right).$

Let $\alpha=k_{2,2}-\frac{k_{1,2}k_{2,1}}{k_{1,1}}$. Since
$k_{2,2}\not\in{\mbox{\conj Q}}[k_{1,1},k_{1,2},k_{2,1}]$ by construction,
$\alpha\neq 0$ and we can continue reducing the matrix to echelon form. Then
multiplying the second row by $\frac{1}{\alpha}$ we obtain

$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&\frac{1}{k_{1,1}}&0\\\
0&1&\frac{1}{\alpha}(k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}})&\dots&\frac{1}{\alpha}(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}})&-\frac{k_{2,1}}{\alpha
k_{1,1}}&\frac{1}{\alpha}\\\
0&k_{3,2}-\frac{k_{1,2}k_{3,1}}{k_{1,1}}&k_{3,3}-\frac{k_{1,3}k_{3,1}}{k_{1,1}}&\dots&k_{3,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{3,1}}{k_{1,1}}&0&0\end{array}\right).$

Let $\beta=k_{3,2}-\frac{k_{1,2}k_{3,1}}{k_{1,1}}$. Multiplying the second row
by $-\beta$ and adding the result to the third row we get

$\left(\begin{array}[]{ccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&\frac{1}{k_{1,1}}&0\\\
0&1&\frac{1}{\alpha}(k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}})&\dots&\frac{1}{\alpha}(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}})&-\frac{k_{2,1}}{\alpha
k_{1,1}}&\frac{1}{\alpha}\\\
0&0&\rho_{3,3}&\dots&\rho_{3,\Delta(\overline{G})+1}&\frac{-k_{3,1}}{k_{1,1}}+\frac{k_{2,1}\beta}{\alpha
k_{1,1}}&\frac{-\beta}{\alpha}\end{array}\right)$

where
$\rho_{3,3}=k_{3,3}-\frac{k_{1,3}k_{3,1}}{k_{1,1}}-\frac{\beta}{\alpha}(k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}}),\dots,\rho_{3,\Delta(\overline{G})+1}=k_{3,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{3,1}}{k_{1,1}}-\frac{\beta}{\alpha}(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}})$.
Note that $\rho_{3,3}\neq 0$ otherwise $k_{3,3}$ belongs to a field extension
of the lattice $L[{\mbox{\conj
Q}}[k_{1,1},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})+1},k_{3,1},k_{3,2}]]$
which is a contradiction.

Thus, multiplying the third row by $\frac{1}{\rho_{3,3}}$ we obtain the
echelon form of the homogeneous system

$\left(\begin{array}[]{cccccccc}1&\frac{k_{1,2}}{k_{1,1}}&\frac{k_{1,3}}{k_{1,1}}&\frac{k_{1,4}}{k_{1,1}}&\dots&\frac{k_{1,\Delta(\overline{G})+1}}{k_{1,1}}&\frac{1}{k_{1,1}}&0\\\
0&1&\frac{1}{\alpha}(k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}})&\frac{1}{\alpha}(k_{2,4}-\frac{k_{1,4}k_{2,1}}{k_{1,1}})&\dots&\frac{1}{\alpha}(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}})&-\frac{k_{2,1}}{\alpha
k_{1,1}}&\frac{1}{\alpha}\\\
0&0&1&\frac{\rho_{3,4}}{\rho_{3,3}}&\dots&\frac{\rho_{3,\Delta(\overline{G})+1}}{\rho_{3,3}}&\zeta&\frac{-\beta}{\rho_{3,3}\alpha}\end{array}\right)$

where all the values $\rho_{3,j}\neq 0,j=4,\dots,\Delta(\overline{G})+1$ as
well as
$\zeta=\frac{-k_{3,1}}{\rho_{3,3}k_{1,1}}+\frac{k_{2,1}\beta}{\rho_{3,3}\alpha
k_{1,1}}$ and $\frac{-\beta}{\rho_{3,3}\alpha}$ are nonzero. Then we can
choose values $k_{4,4},\dots,k_{4,\Delta(\overline{G})+1},g_{4,1},g_{4,2}$
nonzero and chosen one by one from different field extensions not in the
lattice

$L[{\mbox{\conj Q}}[k_{1,1}],\dots,{\mbox{\conj
Q}}[k_{1,\Delta(\overline{G})+1}],{\mbox{\conj Q}}[k_{2,1}],\dots,{\mbox{\conj
Q}}[k_{2,\Delta(\overline{G})+1}],{\mbox{\conj Q}}[k_{3,1}],\\\
\dots,{\mbox{\conj Q}}[k_{3,\Delta(\overline{G})+1}]$

in the following way.

  1. $k_{4,4}\not\in{\mbox{\conj Q}}[k_{i,j}],i=1,2,3,j=1,\dots,\Delta(\overline{G})+1$,

  2. $k_{4,3}\not\in{\mbox{\conj Q}}[k_{i,j},k_{4,4}],i=1,2,3,j=1,\dots,\Delta(\overline{G})+1$,

  3. $\vdots$

  4. $k_{4,\Delta(\overline{G})+1}\not\in{\mbox{\conj Q}}[k_{i,j},k_{4,4},\dots,k_{4,\Delta(\overline{G})}],i=1,2,3,j=1,\dots,\Delta(\overline{G})+1$,

  5. $g_{4,1}\not\in{\mbox{\conj Q}}[k_{i,j},k_{4,4},\dots,k_{4,\Delta(\overline{G})+1}],i=1,2,3,j=1,\dots,\Delta(\overline{G})+1$,

  6. $g_{4,2}\not\in{\mbox{\conj Q}}[k_{i,j},k_{4,4},\dots,k_{4,\Delta(\overline{G})+1},g_{4,1}],i=1,2,3,j=1,\dots,\Delta(\overline{G})+1$,

Therefore $k_{4,3},k_{4,2}$, and $k_{4,1}$ become

$\displaystyle k_{4,3}$ $\displaystyle=$
$\displaystyle-\frac{\rho_{3,4}k_{4,4}}{\rho_{3,3}}+\dots-\frac{\rho_{3,\Delta(\overline{G})+1}k_{4,\Delta(\overline{G})+1}}{\rho_{3,3}}+\frac{k_{3,1}g_{4,1}}{\rho_{3,3}k_{1,1}}-\frac{k_{2,1}\beta
g_{4,1}}{\rho_{3,3}\alpha k_{1,1}}+\frac{\beta g_{4,2}}{\rho_{3,3}\alpha}.$
$\displaystyle k_{4,2}$ $\displaystyle=$
$\displaystyle-(\frac{1}{\alpha}(k_{2,3}-\frac{k_{1,3}k_{2,1}}{k_{1,1}}))k_{4,3}-\dots-(\frac{1}{\alpha}(k_{2,\Delta(\overline{G})+1}-\frac{k_{1,\Delta(\overline{G})+1}k_{2,1}}{k_{1,1}}))k_{4,\Delta(\overline{G})+1}$
$\displaystyle+\frac{k_{2,1}g_{4,1}}{\alpha k_{1,1}}-\frac{g_{4,2}}{\alpha}$
$\displaystyle k_{4,1}$ $\displaystyle=$
$\displaystyle-\frac{k_{1,2}k_{4,2}}{k_{1,1}}-\dots-\frac{k_{1,\Delta(\overline{G})+1}k_{4,\Delta(\overline{G})+1}}{k_{1,1}}-\frac{g_{4,1}}{k_{1,1}}$

Note that $k_{4,1}$ depends on $k_{4,2}$ and $k_{4,3}$. Similarly $k_{4,2}$
depends on $k_{4,3}$. Therefore we should choose $k_{4,3}$ first and then back
substitute. But $k_{4,3}$ depends on $g_{4,1}$ and $g_{4,2}$ which are free
variables with the restriction that they cannot be zero. Thus, we can choose
$g_{4,1}$ in a field extension not in the lattice of

$Q[k_{1,1},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})+1},k_{3,1},\dots,k_{3,\Delta(\overline{G})+1},k_{4,4},\dots,k_{4,\Delta(\overline{G})+1}]$

and $g_{4,2}$ in some field extension not in the lattice of

$Q[k_{1,1},\dots,k_{1,\Delta(\overline{G})+1},k_{2,1},\dots,k_{2,\Delta(\overline{G})+1},k_{3,1},\dots,k_{3,\Delta(\overline{G})+1},\\\
k_{4,4},\dots,k_{4,\Delta(\overline{G})+1},g_{4,1}]$

in such a way that $k_{4,3},k_{4,2}$ and $k_{4,1}$ are nonzero.

As a consequence, the system $S$ is consistent and there exist a solution of
values $k_{4,j}\neq 0,\ j=1,2,\dots,\Delta(\overline{G})+1$ chosen from
different field extensions such that the vector $\overrightarrow{v_{4}}$
satisfies all adjacency conditions and orthogonal conditions with the vectors
$\overrightarrow{v_{1}},\overrightarrow{v_{2}},\overrightarrow{v_{3}}$. Then
the vector
$\overrightarrow{v_{4}}=\sum_{j=1}^{\Delta(\overline{G})+1}k_{4,j}\overrightarrow{e_{j}}$
satisfies conditions (1) and (2) and therefore
$\\{\overrightarrow{v_{1}},\overrightarrow{v_{2}},\overrightarrow{v_{3}},\overrightarrow{v_{4}}\\}$
is an orthogonal representation of $Y_{4}$ in ${\mbox{\conj
R}}^{\Delta(\overline{G})+1}$.
Case 3 . $v_{4}\sim v_{1},v_{4}\not\sim v_{2},v_{4}\sim v_{3}$ in $G$.
From the adjacency conditions $v_{4}\sim v_{1},v_{4}\sim v_{3}$ and orthogonal
condition $v_{4}\not\sim v_{2}$ we get the equations:

$\displaystyle\langle\overrightarrow{v_{1}},\overrightarrow{v_{4}}\rangle$
$\displaystyle=$ $\displaystyle g_{4,1},g_{4,1}\neq 0$
$\displaystyle\langle\overrightarrow{v_{2}},\overrightarrow{v_{4}}\rangle$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle\langle\overrightarrow{v_{3}},\overrightarrow{v_{4}}\rangle$
$\displaystyle=$ $\displaystyle g_{4,2},g_{4,2}\neq 0$

Interchanging the second and third equations we get a system $S$ similar to
case 2. Since all the scalars
$k_{i,j},i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$ are not zero and were
chosen from different field extensions the same reasoning as in case 2 applies
and the conclusion holds for case 3.
Case 4. $v_{4}\not\sim v_{1},v_{4}\sim v_{2},v_{4}\sim v_{3}$ in $G$.

From the adjacency conditions $v_{4}\sim v_{2},v_{4}\sim v_{3}$ and orthogonal
condition $v_{4}\not\sim v_{1}$ we get the equations:

$\displaystyle\langle\overrightarrow{v_{1}},\overrightarrow{v_{4}}\rangle$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle\langle\overrightarrow{v_{2}},\overrightarrow{v_{4}}\rangle$
$\displaystyle=$ $\displaystyle g_{4,2},g_{4,2}\neq 0$
$\displaystyle\langle\overrightarrow{v_{3}},\overrightarrow{v_{4}}\rangle$
$\displaystyle=$ $\displaystyle g_{4,3},g_{4,3}\neq 0.$

Interchanging the first and the third equations we get a system $S$ similar to
case 2. Since all the scalars
$k_{i,j},i=1,2,3,j=1,2,\dots,\Delta(\overline{G})+1$ are not zero and were
chosen from different field extensions the same reasoning as in case 2 applies
and the conclusion holds for case 4.

As a consequence, in all of the cases we get an orthogonal representation for
$Y_{4}$ in ${\mbox{\conj R}}^{\Delta(\overline{G})+1}$ satisfying the
conditions (1) and (2). This completes of the proof of the claim 4.6.

Assume that for any
$Y_{m-1}=(V_{Y_{m-1}},E_{Y_{m-1}}),V_{Y_{m-1}}=\\{v_{1},v_{2},\dots,v_{m-1}\\}$
it is possible to get an orthogonal representation of $Y_{m-1}$ in
${\mbox{\conj R}}^{\Delta(\overline{G})+1}$. Let
$\overrightarrow{v}_{1},\overrightarrow{v}_{2},\dots,\overrightarrow{v}_{m-1}$
be of the form

$\overrightarrow{v}_{i}=\displaystyle{\sum_{j=1}^{\Delta(\overline{G})+1}k_{i,j}\overrightarrow{e}_{j}}$

satisfying conditions (1) and (2) where $k_{i,j}\neq 0$ for all
$i=1,2,\dots,m,j=1,2,\dots,\Delta(\overline{G})+1$ , chosen from different
field extensions.

We need to prove that if $v_{m}$ is adjoined to $Y_{m-1}$ to get $Y_{m}$ such
that $v_{m}$ is adjacent to all prior vertices except at most
$\left\lfloor\frac{m}{2}-1\right\rfloor$ vertices then $Y_{m}$ has an
orthogonal representation of vectors
$\overrightarrow{v}_{1},\overrightarrow{v}_{2},\dots,\overrightarrow{v}_{m}$
in ${\mbox{\conj R}}^{\Delta(G)+1}$ satisfying conditions (1) and (2). Assume
that $v_{m}$ has an associated vector $\overrightarrow{v}_{m}$ such that

$\overrightarrow{v}_{m}=k_{1}^{m}\overrightarrow{e_{1}}+k_{2}^{m}\overrightarrow{e_{2}}+\dots+k_{\Delta(\overline{G})+1}^{m}\overrightarrow{e}_{\Delta(\overline{G})+1}.$

The vertex $v_{m}$ is adjacent to all prior vertices
$v_{1},v_{2},\dots,v_{m-1}$ except at most
$t\leq\left\lfloor\frac{m}{2}-1\right\rfloor$ vertices in $G$. Then we see
that $\overrightarrow{v}_{m}$ satisfies at least $m-1-t$ adjacency conditions
and $t$ orthogonal conditions.

Let $\rho$ be a permutation of $(1,2,\dots,m-1)$. Suppose
$v_{\rho(1)},v_{\rho(2)},\dots,v_{\rho(m-1-t)}$ are adjacent to $v_{m}$ and
$v_{\rho(m-t)},v_{\rho(m-t+1)},\dots,v_{\rho(m-2)},v_{\rho(m-1)}$ are not
adjacent to $v_{m}$. The vectors
$\overrightarrow{v}_{\rho(1)},\overrightarrow{v}_{\rho(2)},\dots,\\\
\overrightarrow{v}_{\rho(m-1-t)},\overrightarrow{v}_{\rho(m-t)},\overrightarrow{v}_{\rho(m-t+1)},\dots,\overrightarrow{v}_{\rho(m-1)}$
and $\overrightarrow{v}_{m}$ satisfy the system $S$ given by:

$\displaystyle\langle\overrightarrow{v}_{\rho(1)},\overrightarrow{v}_{m}\rangle$
$\displaystyle=$ $\displaystyle g_{m,1},\ \ g_{m,1}\neq 0$
$\displaystyle\langle\overrightarrow{v}_{\rho(2)},\overrightarrow{v}_{m}\rangle$
$\displaystyle=$ $\displaystyle g_{m,2},\ \ g_{m,2}\neq 0$
$\displaystyle\vdots$ $\displaystyle\vdots$ $\displaystyle\vdots$
$\displaystyle\langle\overrightarrow{v}_{\rho(m-1-t)},\overrightarrow{v}_{m}\rangle$
$\displaystyle=$ $\displaystyle g_{m,m-1-t},\ \ g_{m,m-1-t}\neq 0$
$\displaystyle\langle\overrightarrow{v}_{\rho(m-t)},\overrightarrow{v}_{m}\rangle$
$\displaystyle=$ $\displaystyle 0$
$\displaystyle\langle\overrightarrow{v}_{\rho(m-t+1)},\overrightarrow{v}_{m}\rangle$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle\vdots$ $\displaystyle\vdots$
$\displaystyle\vdots$
$\displaystyle\langle\overrightarrow{v}_{\rho(m-1)},\overrightarrow{v}_{m}\rangle$
$\displaystyle=$ $\displaystyle 0$

containing $m-1-t$ equations from the adjacency conditions and $t$ equations
from the orthogonal conditions. Since the vector
$\overrightarrow{v}_{\rho(i)},i=1,2,\dots,m-1$ has the form

$\overrightarrow{v}_{\rho(i)}=k_{\rho(i),1}\overrightarrow{e}_{1}+k_{\rho(i),2}\overrightarrow{e}_{2}+\dots+k_{\rho(i),\Delta(\overline{G})+1}\overrightarrow{e}_{\Delta(\overline{G})+1}$
(5)

where all $k_{\rho(i),j},i=1,2,\dots,m-1,j=1,2,\dots,\Delta(\overline{G})+1$
are not zero and chosen from different field extensions, the system $S$ has
the form:

$\displaystyle
k_{\rho(1),1}k_{m,1}+k_{\rho(1),2}k_{m,2}+\dots+k_{\rho(1),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle g_{m,1}$ $\displaystyle
k_{\rho(2),1}k_{m,1}+k_{\rho(2),2}k_{m,2}+\dots+k_{\rho(2),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle g_{m,2}$ $\displaystyle\vdots$
$\displaystyle\vdots$ $\displaystyle\vdots$ $\displaystyle
k_{\rho(m-1-t),1}k_{m,1}+k_{\rho(m-1-t),2}k_{m,2}+\dots+k_{\rho(m-1-t),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle g_{m,m-1-t}$ $\displaystyle
k_{\rho(m-t),1}k_{m,1}+k_{\rho(m-t),2}k_{m,2}+\dots+k_{\rho(m-t),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle
k_{\rho(m-t+1),1}k_{m,1}+k_{\rho(m-t+1),2}k_{m,2}+\dots+k_{\rho(m-t+1),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle\vdots$ $\displaystyle\vdots$
$\displaystyle\vdots$ $\displaystyle
k_{\rho(m-1),1}k_{m,1}+k_{\rho(m-1),2}k_{m,2}+\dots+k_{\rho(m-1),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle 0$

where $g_{m,1}\neq 0,g_{m,2}\neq 0,\dots,g_{m,m-1-t}\neq 0$. Since
$g_{m,1},g_{m,2},\dots,g_{m,m-1-t}$ could be any nonzero real numbers
satisfying the adjacency conditions we can consider them as additional $m-1-t$
variables under the restriction that they cannot be zero. Therefore we can
consider a homogeneous system $S_{H}$ of $m-1$ equations in
$m-t+\Delta(\overline{G})$ variables
$k_{1}^{m},k_{2}^{m},\dots,k_{\Delta(\overline{G})+1}^{m},-g_{m,1},-g_{m,2},\\\
\dots,-g_{m,m-1-t}$. Now, by hypothesis
$t\leq\left\lfloor\frac{m}{2}-1\right\rfloor$. Since $t\leq
d_{\overline{G}}(v_{m})\leq\Delta(\overline{G})<\Delta(\overline{G})+1$ the
homogeneous system $S_{H}$ contains at least one more variable than the number
of equations. Hence the system $S_{H}$ given by

$\displaystyle
k_{\rho(1),1}k_{m,1}+k_{\rho(1),2}k_{m,2}+\dots+k_{\rho(1),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}+(-g_{m,1})$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle
k_{\rho(2),1}k_{m,1}+k_{\rho(2),2}k_{m,2}+\dots+k_{\rho(2),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}+(-g_{m,2})$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle\vdots$ $\displaystyle\vdots$
$\displaystyle\vdots$ $\displaystyle
k_{\rho(m-1-t),1}k_{m,1}+k_{\rho(m-1-t),2}k_{m,2}+\dots+k_{\rho(m-1-t),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}+(-g_{m,m-1-t})$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle
k_{\rho(m-t+),1}k_{m,1}+k_{\rho(m-t),2}k_{m,2}+\dots+k_{\rho(m-t),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle
k_{\rho(m-t+1),1}k_{m,1}+k_{\rho(m-t+1),2}k_{m,2}+\dots+k_{\rho(m-t+1),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle 0$ $\displaystyle\vdots$ $\displaystyle\vdots$
$\displaystyle\vdots$ $\displaystyle
k_{\rho(m-1),1}k_{m,1}+k_{\rho(m-1),2}k_{m,2}+\dots+k_{\rho(m-1),\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}$
$\displaystyle=$ $\displaystyle 0$

has infinitely many solutions. Therefore, it is enough to show that there
exist at least one solution for $S_{H}$ satisfying the condition that none of
the $k_{m,1},k_{m,2},\dots,k_{m,\Delta(\overline{G})+1},g_{m,1},\\\
\dots,g_{m,m-1-t}$ are zero. This implies that the system $S$ has a solution
which satisfies all adjacency conditions, all orthogonal conditions, and
conditions (1) and (2). For that purpose consider the
$(m-1)\times(m-t+\Delta(\overline{G}))$ matrix $A$ of the homogeneous system
given on the next page.

Let $\overrightarrow{g}=(-g_{m,1},-g_{m,2},\dots,-g_{m,m-1-t})^{T}$. We
consider the two cases where $m-1\leq\Delta(\overline{G})+1$ and
$m-1>\Delta(\overline{G})+1$.

Case 1. $m-1\leq\Delta(\overline{G})+1$

In this case the number of equations in the non-homogeneous system $S$ is at
most the number of unknowns
$k_{m,1},k_{m,2},\dots,k_{m,\Delta(\overline{G})+1}$.

$A=\left(\begin{array}[]{ccccccccccc}k_{\rho(1),1}&k_{\rho(1),2}&k_{\rho(1),3}&\dots&k_{\rho(1),\Delta(\overline{G})+1}&|&1&0&\dots&0&0\\\
k_{\rho(2),1}&k_{\rho(2),2}&k_{\rho(2),3}&\dots&k_{\rho(2),\Delta(\overline{G})+1}&|&0&1&\dots&0&0\\\
k_{\rho(3),1}&k_{\rho(3),2}&k_{\rho(3),3}&\dots&k_{\rho(3),\Delta(\overline{G})+1}&|&0&0&1&\vdots&\vdots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
k_{\rho(m-t-2),1}&k_{\rho(m-t-2),2}&k_{\rho(m-t-2),3}&\dots&k_{\rho(m-t-2),\Delta(\overline{G})+1}&|&0&0&0&1&0\\\
k_{\rho(m-t-1),1}&k_{\rho(m-t-1),2}&k_{\rho(m-t-1),3}&\dots&k_{\rho(m-t-1),\Delta(\overline{G})+1}&|&0&0&0&0&1\\\
k_{\rho(m-t),1}&k_{\rho(m-t),2}&k_{\rho(m-t),3}&\dots&k_{\rho(m-t),\Delta(\overline{G})+1}&|&0&0&0&0&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
k_{\rho(m-1),1}&k_{\rho(m-1),2}&k_{\rho(m-1),3}&\dots&k_{\rho(m-1),\Delta(\overline{G})+1}&|&0&0&0&0&0\end{array}\right)$

Thus $A$ can be row reduced to one of the following two echelon form written
in block form:

  1. I.

$B=\left(B_{1}|B_{2}\right)={\tiny\left(\begin{array}[]{cccccccccccccccccc}1&\ast&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast&\dots&\ast&|&\delta_{1}&0&\dots&0&0\\\
0&1&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast&\dots&\ast&|&\ast&\delta_{2}&\dots&0&0\\\
0&0&1&\dots&\ast&\ast&\ast&\dots&\ast&\ast&\dots&\ast&|&\ast&\ast&\delta_{3}&0&0\\\
\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\dots&\vdots&|&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&1&\ast&\ast&\dots&\ast&\ast&\dots&\ast&|&\ast&\ast&\dots&\delta_{m-2-t}&0\\\
0&0&0&\dots&0&1&\ast&\dots&\ast&\ast&\dots&\ast&|&\ast&\ast&\dots&\ast&\delta_{m-1-t}\\\
0&0&0&\dots&0&0&1&\dots&\ast&\ast&\dots&\ast&|&\ast&\ast&\dots&\ast&\ast\\\
\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\dots&\vdots&|&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&0&0&0&\dots&1&\ast&\dots&\ast&|&\ast&\ast&\dots&\ast&\ast\\\
\end{array}\right)}$

  2. II.

$B=\left(B_{3}|B_{2}\right)={\tiny\left(\begin{array}[]{cccccccccccc}1&\ast&\ast&\dots&\ast&\ast&|&\delta_{1}&0&\dots&0&0\\\
0&1&\ast&\dots&\ast&\ast&|&\ast&\delta_{2}&\dots&0&0\\\
0&0&1&\dots&\ast&\ast&|&\ast&\ast&\delta_{3}&0&0\\\
\vdots&\vdots&\vdots&\dots&\vdots&\vdots&|&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&1&\ast&|&\ast&\ast&\dots&\delta_{m-t-1}&0\\\
0&0&0&\dots&0&1&|&\ast&\ast&\dots&\ast&\delta_{m-t}\\\ \end{array}\right)}.$

The matrix $B_{1}$ is a block of size $(m-1)\times(\Delta(\overline{G})+1)$
where $m-1<\Delta(\overline{G})+1$. The matrix $B_{2}$ is a block matrix of
size $(m-1)\times(m-1-t)$. Matrix $B_{3}$ is a square matrix of size
$m-1(=\Delta(\overline{G})+1)$. In these blocks $\ast$ denotes a nonzero
entry.

Suppose matrix $B$ is of type I. For each vector
$\overrightarrow{v}_{i},i=4,5,\dots,m-1$ the entries are found in field
extensions which are not in the lattice of the previous field extensions.

In the block matrix $B_{2}$ we have:

  * $[B_{2}]_{1,1}=\delta_{1}=\frac{1}{k_{\rho(1),1}}\neq 0$,

  * $[B_{2}]_{2,2}=\delta_{2}=\left(k_{\rho(2),2}-\frac{k_{\rho(1),2}\cdot k_{\rho(2),1}}{k_{\rho(1),1}}\right)^{-1}\neq 0$.

  * $[B_{2}]_{3,3}=\delta_{3}=\frac{1}{\alpha}\neq 0,\alpha\in Q[k_{\rho(1),1},k_{\rho(1),2},k_{\rho(1),3},k_{\rho(2),1},k_{\rho(2),2},k_{\rho(2),3},k_{\rho(3),1},k_{\rho(3),2},k_{\rho(3),3}]$.

Continuing this process we get that all the entries on the diagonal of $B_{2}$
to be nonzero. So all the rows of $B_{2}$ have at least one entry
nonzero.Thus,

  * $\left[B_{2}\overrightarrow{g}\right]_{1}=-\delta_{1}\cdot g_{m,1}=\frac{-g_{m,1}}{k_{1,1}}$. Choosing $g_{m,1}$ not in the lattice generated by the previous field extensions for $k_{i,j},i=1,2,\dots,m-1,j=1,2,\dots,\Delta(\overline{G})+1$, we get $\left[B_{2}\overrightarrow{g}\right]_{1}\neq 0$.

  * $\left[B_{2}\overrightarrow{g}\right]_{2}=\alpha_{2,1}g_{m,1}+\delta_{2}g_{m,2},\alpha_{2,1}\neq 0,\delta_{2}\neq 0$. Then we can choose a value for $g_{m,2}$ from a field extension not in the lattice of fields generated by the previous values $k_{i,j},i=1,2,\dots,m-1,j=1,2,\dots,\Delta(G)+1,g_{m,1}$ so that $\left[B_{2}\overrightarrow{g}\right]_{2}\neq 0$.

  * $\left[B_{2}\overrightarrow{g}\right]_{3}=\alpha_{3,1}g_{m,1}+\alpha_{3,2}g_{m,2}+\delta_{3}g_{m,3},\alpha_{3,1}\neq 0,\delta_{3}\neq 0$. As above we can choose $g_{m,3}\neq 0$ and such that $\left[B_{2}\overrightarrow{g}\right]_{3}\neq 0$ by taking $g_{m,3}$ neither in $Q[\frac{\alpha_{3,1}g_{m,1}+\alpha_{3,2}g_{m,2}}{-\delta_{3}}]$ nor in any of the previous field extensions.

Continuing this process and applying similar choices we see that
$g_{m,4},g_{m,5}\dots,g_{m,m-1}$ can be chosen nonzero. Moreover, matrix
$B_{1}$ shows that there is at least one free variable for the solution of
$k_{m,j},j=1,2,\dots,\Delta(\overline{G})+1$. All of these free variables can
be chosen in different field extensions such that all other unknowns are not
zero. Otherwise it is possible to show that the last choice belongs to the
field containing all the previous chosen values which is a contradiction. Now,
suppose that $k_{m,1},k_{m,2},\\\ \dots,k_{m,r},r<\Delta(\overline{G})+1$ can
be written in terms of $k_{m,r+1},\dots,k_{m,\Delta(\overline{G}+1)}$ as

$k_{m,i}=\alpha_{r+1}k_{m,r+1}+\dots+\alpha_{\Delta(\overline{G})+1}k_{m,\Delta(\overline{G})+1}+\varphi_{i}(g_{m,1},g_{m,2},\dots,g_{m,m-1}),i=1,2,\dots,r$
(6)

where $\alpha_{r+1},\dots,\alpha_{\Delta(\overline{G})+1}$ are all nonzero and
$\varphi_{i}$ is a linear combination of $g_{m,1},\dots,g_{m,m-1}$. Also
$\varphi_{i}(g_{m,1},g_{m,2},\dots,g_{m,m-1})\neq 0,i=1,2,\dots,r$. Thus,by
choosing values
$k_{m,r+1},\dots,k_{m,\Delta(\overline{G})+1}$ in different field extensions
and substituting them in 6, we obtain that $k_{m,i}\neq 0,i=1,2,\dots,r$.

As a consequence, the vector $\overrightarrow{v}_{m}$ exists and all of its
entries are nonzero.

If matrix $B$ is of type II we apply same process as in case of type I. Again,
we can obtain the vector $v_{m}$ having all its entries nonzero and
$g_{m,i}\neq 0$ for $i=1,\dots,m-1$.

Case 2. $m-1>\Delta(\overline{G})+1$

In this case the number of equations in the non-homogeneous system $S$ is more
than the number of unknowns
$k_{m,1},k_{m,2},\dots,k_{m,\Delta(\overline{G})+1}$.

We need to analyze three possible subcases where
$m-1-t<\Delta(\overline{G})+1,m-1-t=\Delta(\overline{G})+1$ or
$m-1-t>\delta(\overline{G})+1$.

  1. 1.

If $m-1-t<\Delta(\overline{G})+1$ then matrix $B$ has the form

$B={\tiny\left(\begin{array}[]{cccccccccccccccccc}1&\ast&\ast&\dots&\ast&|&\ast&\dots&\ast&|&\ast&0&0&0&0&\dots&0&0\\\
0&1&\ast&\dots&\ast&|&\ast&\dots&\ast&|&\ast&\ast&0&0&0&\dots&0&0\\\
0&0&1&\dots&\ast&|&\ast&\dots&\ast&|&\ast&\ast&\ast&0&0&\dots&0&0\\\
\vdots&\vdots&\vdots&\dots&\vdots&|&\vdots&\dots&\vdots&|&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&1&|&\ast&\dots&\ast&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
-&-&-&-&-&-&-&\dots&-&|&-&-&-&-&-&\dots&-&-\\\
0&0&0&\dots&0&|&1&\dots&\ast&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
\vdots&\vdots&\vdots&\vdots&\vdots&|&\vdots&\dots&\vdots&|&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&0&|&0&\dots&\ast&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
0&0&0&\dots&0&|&0&\dots&1&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
0&0&0&\dots&0&|&0&\dots&0&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
\vdots&\vdots&\vdots&\vdots&\vdots&|&\vdots&\dots&\vdots&|&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&0&|&0&\dots&0&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast\end{array}\right)}$
$B=\left(\begin{array}[]{ccc}B_{1}&B_{2}&B_{3}\\\ B_{4}&B_{5}&B_{6}\\\
\end{array}\right)$

The matrix $B_{1}$ is a square matrix $(m-1-t)\times(m-1-t)$, matrix $B_{2}$
has size $(m-1-t)\times(\Delta(\overline{G})+2+t-m)$, matrix $B_{3}$ is a
square matrix of size $m-1-t$. Matrix $B_{4}$ is a zero matrix of size
$t\times m-1-t$. The central blocks $B_{2},B_{5}$ form a block of size
$(m-1)\times(\Delta(\overline{G})+2+t-m)$ and corresponds to the columns of
free variables $k_{m,m-t},\dots,k_{m,\Delta(\overline{G})+1}$ of the system
$S$. The block $B_{6}$ has size $t\times(m-1-t)$ .

Consider the block matrix $\left(B_{5}\ B_{6}\right)$ of size
$t\times(\Delta(\overline{G})+1)$. Recalling that the value $t$ is the number
of orthogonal conditions for $v_{m}$ in $G$ which is equivalent to
$\mathop{{\rm{d}}}\nolimits_{\overline{G}}(v_{m})$ we get
$t\leq\Delta(\overline{G})<\Delta(\overline{G})+1$. As a consequence, the
homogeneous system $\left(B_{5}\ B_{6}\right)\overrightarrow{w}=0$ where
$\overrightarrow{w}$ is a vector of size $(\Delta(\overline{G})+1)\times 1$ in
the variables
$k_{m,m-t},\dots,k_{m,\Delta(\overline{G})+1},(-g_{m,1}),\dots,\\\
(-g_{m,m-1-t})$, has infinitely many solutions depending on at least one free
variable. Choosing these free variables in different field extensions as we
did previously, we get nonzero values for $k_{m,m-t},\\\
\dots,k_{m,\Delta(\overline{G})+1},g_{m,1},\dots,g_{m,m-1-t}$. We get the
values of the remaining unknowns $k_{m,i},i=1,2,\dots,m-1-t$ of the system $S$
applying back substitution. Since all the entries with $\ast$ in the block
$B_{1}$ are nonzero and belong to different field extensions, the values
$k_{m,i},i=1,2,\dots,m-1-t$ are also nonzero.

As a consequence, the non-homogeneous system $S$ is consistent and the vector
$v_{m}$ with no zero entries exists.

  2. 2.

If $m-1-t=\Delta(\overline{G})+1$ then the matrix $B$ has the form

$\displaystyle B$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{ccc}B_{1}&|&B_{2}\\\ -&&-\\\ 0&|&R\\\
\end{array}\right)$ $\displaystyle=$
$\displaystyle{\tiny\left(\begin{array}[]{cccccccccccccccc}1&\ast&\ast&\dots&\ast&\dots&\ast&|&\delta_{1}&0&0&0&0&\dots&0&0\\\
0&1&\ast&\dots&\ast&\dots&\ast&|&\ast&\delta_{2}&0&0&0&\dots&0&0\\\
0&0&1&\dots&\ast&\dots&\ast&|&\ast&\ast&\delta_{3}&0&0&\dots&0&0\\\
\vdots&\vdots&\vdots&\dots&\vdots&\dots&\vdots&|&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&1&\dots&\ast&|&\ast&\dots&\ast&\ast&\ast&\dots&0&0\\\
0&0&0&\dots&0&\dots&\ast&|&\ast&\dots&\ast&\ast&\ast&\dots&\delta_{m-t-2}&0\\\
0&0&0&\dots&0&\dots&1&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\delta_{m-1-t}\\\
-&-&-&-&-&\dots&-&|&-&-&-&-&-&\dots&-&-\\\
0&0&0&\dots&0&\dots&0&|&1&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&0&\dots&0&|&0&\dots&1&\ast&\ast&\dots&\ast&\ast\end{array}\right)}.$

In this case the matrices $B_{1}$ and $B_{2}$ are square matrices of size
$m-1-t(=\Delta(\overline{G})+1)$. The matrix $R$ has size $t\times m-1-t$.
Since $t<\left\lfloor\frac{m}{2}-1\right\rfloor$ we get that $2t<m-2<m-1$
which implies that $t<m-1-t$.

Therefore the system $R\overrightarrow{g}=0$ has infinitely many solutions
with $m-1-2t$ free variables. Taking the free variables from different field
extensions we get all the values $g_{m,1}\dots,g_{m,m-1-t}$ nonzero.
Substituting $g_{m,1}\dots,g_{m,m-1-t}$ in the equations of the system
$B_{2}\overrightarrow{g}=0$ we get $[B_{2}\overrightarrow{g}]_{i}\neq 0$ for
all $i=1,\dots,m-1-t$. Otherwise, it is possible to show that the last choice
belongs to the field containing all previous chosen values which is a
contradiction. This implies that
$k_{m,\Delta(\overline{G})+1}=[B_{2}\overrightarrow{g}]_{m-1-t}\neq 0$ from
the last row of $(B_{1}\ B_{2})$.

Applying back substitution and similar argument with
$g_{m,1}\dots,g_{m,m-1-t}$ we conclude that
$k_{m,1},\dots,k_{m,\Delta(\overline{G})}$ are also nonzero. Thus the system
$S$ has a solution with nonzero values for the unknowns. As a consequence
there exists a vector $\overrightarrow{v}_{m}$ satisfying all the adjacency
conditions and orthogonal conditions.

  3. 3.

$m-1-t>\Delta(\overline{G})+1$ then matrix $B$ has the form

$B=\left(\begin{array}[]{ccc}B_{1}&|&B_{2}\\\ -&&-\\\ 0&|&R\\\
\end{array}\right)={\tiny\left(\begin{array}[]{cccccccccccccccc}1&\ast&\ast&\dots&\ast&\dots&\ast&|&\ast&0&0&0&0&\dots&0&0\\\
0&1&\ast&\dots&\ast&\dots&\ast&|&\ast&\ast&0&0&0&\dots&0&0\\\
0&0&1&\dots&\ast&\dots&\ast&|&\ast&\ast&\ast&0&0&\dots&0&0\\\
\vdots&\vdots&\vdots&\dots&\vdots&\dots&\vdots&|&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&1&\dots&\ast&|&\ast&\dots&\ast&\ast&\ast&\dots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&0&\dots&\ast&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&0\\\
0&0&0&\dots&0&\dots&1&|&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
-&-&-&-&-&\dots&-&|&-&-&-&-&-&\dots&-&-\\\
0&0&0&\dots&0&\dots&0&|&1&\dots&\ast&\ast&\ast&\dots&\ast&\ast\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&0&\dots&0&|&0&\dots&1&\ast&\ast&\dots&\ast&\ast\end{array}\right)}.$

The matrix $B_{1}$ has size $(m-1-t)\times(\Delta(\overline{G})+1+r),0<r<t$
where $m-1-t=\Delta(\overline{G})+1+r$. This matrix contains the columns of
the unknowns $k_{m,1},\dots,k_{m,\Delta(\overline{G})+1},\\\
(-g_{m,1}),\dots,(-g_{m,r})$.The matrix $B_{2}$ has size
$(m-1-t)\times(\Delta(\overline{G})+1)$. The $0$ matrix has size
$t\times(\Delta(\overline{G})+1+r)$. The matrix $R$ has size
$t\times(\Delta(\overline{G})+1)$.

Since $t\leq\Delta(\overline{G})<\Delta(\overline{G})+1$ the system
$R\overrightarrow{g}=0$ has infinitely many solutions with at least one free
variable. By the same argument as in case 2 we get that the system $S$ is
consistent and the solution with nonzero values for $k_{m,1},\dots
k_{m,\Delta(\overline{G})+1}$ gives a vector $\overrightarrow{v}_{m}$ which
satisfies all the adjacency conditions and orthogonal conditions.

Hence, $Y_{m}$ has an orthogonal representation of vectors in ${\mbox{\conj
R}}^{\Delta(\overline{G})+1}$ satisfying the conditions (1) and (2). Thus
$Y_{|G|}=G$ has an orthogonal representation in ${\mbox{\conj
R}}^{\Delta(\overline{G})+1}$ satisfying conditions (1) and (2).

Using the same argument in the construction of vector $v_{4}$, we prove that
$v_{1},\dots,v_{m}$ is pairwise linearly independent set of vectors in
${\mbox{\conj R}}^{\Delta(\overline{G})+1}$. Finally since
$\mathop{{\rm{msr}}}\nolimits(G)$ is the smallest dimension in which $G$ has
an orthogonal representation
$\mathop{{\rm{msr}}}\nolimits(G)\leq\Delta(\overline{G})+1.$ Since
$\delta(G)+\Delta(\overline{G})=|G|-1$ we conclude that $G$ satisfies the
delta conjecture, namely, $\mathop{{\rm{msr}}}\nolimits(G)\leq|G|-\delta(G).$
$\Box$

######  Observation 4.7.

In the construction of orthogonal representation of the induced graph $Y_{m}$
it is sufficient to consider $t\leq\left\lfloor\frac{m}{2}-1\right\rfloor$ if
$m$ is even and $t<\left\lfloor\frac{m-1}{2}\right\rfloor$ if $m$ is odd. In
both cases we obtain the condition $t<(m-1-t)$ that we need to get infinitely
many solutions for the system $R\overrightarrow{g}=0$. This difference in the
upper bounds for $t$ is important for small values of $m$ but for larger
values of $m$ these upper bounds are asymptotically equivalent. However, it
means that we could get an orthogonal representation of pairwise linearly
independent vectors in ${\mbox{\conj R}}^{\Delta(\overline{G})+1}$ for some
graphs which are not necessarily $\delta$-graphs.

######  Observation 4.8.

Reducing the matrix $A$ to an echelon form needs a finite number of operations
as well as reducing the matrix $R$ to an echelon form. It means that all the
values $k_{i,j},i=1,2,\dots,m-1,j=1,2,\dots,\Delta(\overline{G})+1$ can be
chosen from different field extensions in such a way that all the values
$\ast$ in the reduced echelon form of $A$ are nonzero and belong to different
field extensions.

######  Observation 4.9.

The condition of choosing values $k_{i,j},i=1,2,\dots,|G|,j=1,2,\dots,\\\
\Delta(\overline{G})+1$ from different field extensions was imposed to
guarantee the consistency of the non-homogeneous system $S$. Also, we use this
nonzero entries of the vectors
$\overrightarrow{v}_{1},\dots,\overrightarrow{v}_{m-1}$ to guarantee the
adjacency conditions and orthogonal conditions of the vector
$\overrightarrow{v}_{m}$ corresponding to the newly added vertex. But
calculating the orthogonal representation using this approach could be time
consuming. Since we know that it is possible to get an orthogonal
representation of $\delta$-graph $G$ in ${\mbox{\conj
R}}^{\Delta(\overline{G})+1}$ and since the representation is not unique, it
may be possible to calculate the orthogonal representation using integers or
rational numbers. However, calculating the orthogonal representation of a
$\delta$-graph $G$ in this way could also be tedious because we may need to
apply a backtracking procedure during the calculation due to some adjacency
conditions of the vector corresponding to the newly added vertex may not be
satisfied. When that happens, we may need to go back to some of the previous
vectors and recalculate them until we fix the adjacency conditions.

##  5 Examples of $\delta$-graphs and their $\mathop{{\rm{msr}}}\nolimits$

The result proved above give us a huge family of graph which satisfies delta
conjecture. Since, the complement of a C-$delta$ graphs is a $\delta$-graph,
it is enough to identify a C-$\delta$-graph and therefore we know that its
complement is a $\delta$-graph satisfying delta conjecture.

Some examples of C-$\delta$ graphs that we can find in [15] are the Cartesian
Product $K_{n}\square P_{m},n\geq 3,m\geq 4$, Mobiüs Lader $ML_{2n},n\geq 3$,
Supertriangles $Tn,n\geq 4$, Coronas $S_{n}\circ P_{m},n\geq 2,m\geq 1$ where
$S_{n}$ is a star and $P_{m}$ a path, Cages like Tutte’s (3,8) cage,
Headwood’s (3,6) cage and many others, Blanusa Snarks of type $1$ and $2$ with
$26,34$, and $42$ vértices, Generalized Petersen Graphs $Gp1$ to $Gp16$, and
many others.

In order to show the technique used in the proved result consider the
following example

######  Example 5.1.

If $G$ is the Robertson’s (4,5)-cage on 19 vertices then it is a 4-regular
C-$\delta$ graph. Since $\Delta(G)=4$, the
$\mathop{{\rm{msr}}}\nolimits(G)\leq 5$. To see this is a C-$\delta$ graph it
is enough to label its vertices in the way shown in the next figure:

Figure B.2 Robertson’s (4,5)-cage (19 vertices)

##  6 Conclusion

The result proved above give us a a tool to identify a wide range of families
of graphs which satisfy $\delta$ conjecture. The techniques used in the proof
could be used in future research as a new approach to solve delta conjecture.
However, it is clear that the main problem is still open.

##  7 Acknowledment

I would like to thanks to my advisor Dr. Sivaram Narayan for his guidance and
suggestions of this research. Also I want to thank to the math department of
University of Costa Rica and Universidad Nacional Estatal a Distancia because
their sponsorship during my dissertation research and specially thanks to the
math department of Central Michigan University where I did the researh for
this paper.

## References

  * [1] AIM Minimum Rank-Special Graphs Work Group (Francesco Barioli, Wayne Barrett, Steven Butler, Sebastian M. Cioaba, Shaun M. Fallat, Chris Godsil, Willem Haemers, Leslie Hogben, Rana Mikkelson, Sivaram Narayan, Olga Pryporova, Irene Sciriha, Dragan Stevanovic, Hein Van Der Holst, Kevin Van Der Meulen, and Amy Wangsness), (2008)“Zero Forcing Sets and the Minimum Rank of Graphs”, Linear Algebra and its Applications, 428 1628-1648.
  * [2] Barioli, F et al.(2010) On the Graph Complement Conjecture for Minimum Rank, Linear Algebra and its Applications, in press, doi:10.1016/j.laa.2010.12.024.
  * [3] Barioli, F et al. (2010)Zero Forcing Parameters and Minimum Rank Problems, Linear Algebra and its Applications, 433 401-411.
  * [4] Barioli, F et al .(2011)“Minimum Semidefinite Rank of Outerplanar Graphs and the Tree Cover Number”, Electronic Journal of Linear Algebra, 22 10-21.
  * [5] Barrett, W et al. (2004)Graphs Whose Minimal Rank is Two, Electronic Journal of Linear Algebra, (11) 258-280.
  * [6] Beagley, J et al . (2007) On the Minimum Semidefinite Rank of a Graph Using Vertex Sums, Graphs with $\mathop{{\rm{msr}}}\nolimits(G)=|G|-2$, and the $msr$s of Certain Graphs Classes ,in NSF-REU Report from Central Michigan University (Summer 2007).
  * [7] Berman, A; et al. (2008) An Upper Bound for the Minimum Rank of a Graph, Linear Algebra and its Applications, 429 1629-1638.
  * [8] Bollobás, B . _Modern Graph Theory_ ,Springer.Memphis, TN, 1998.
  * [9] Bondy, J. A. & Murty, U. S. R.(2008) _Graph Theory_ ,Springer.San Francisco, CA.
  * [10] Booth, M, et al. (2011)On the Minimum Semidefinite Rank of a Simple Graph, Linear and Multilinear Algebra, 59 483-506.
  * [11] Booth, M et al. (2008)On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph, SIAM Journal on Matrix Analysis and Applications, 30 731-740.
  * [12] Brandst dt, A et al.(1999)Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X. p 169.
  * [13] Brualdi, R et al. (2007)AIM Workshop Spectra of Families of Matrices described by Graphs, Digraphs, and Sign Patterns Final Report: Mathematical Results (Revised*) Available at http://www.aimath.org/pastworkshop/matrixspectrumrep.pdf,.
  * [14] Chartrand, G et al.(2011) _Graphs & Digraphs_,Taylor & Francis Group. Boca Raton, FL.
  * [15] Diaz, P. (2014)On the delta Conjecture and the Graph Complement Conjecture for Minimum Semidefinite rank of a Graph, Ph.D Dissertation, Central Michigan University.
  * [16] Ekstrand, J et al. (2013)Positive Semidefinite Zero Forcing, Linear Algebra and its Applications, 439 1862-1874.
  * [17] Fallat, S. M. & Hogben, L.(2007) The Minimum Rank of Symmetric Matrices Described by a Graph: A Survey, Linear Algebra and its Applications, 426 558-582.
  * [18] Hackney, P et al. (2009)Linearly Independent Vertices and Minimum Semidefinite Rank, Linear Algebra and its Applications, 431 1105-1115.
  * [19] van der Holst, H. (2003)Graphs whose Positive Semidefinite Matrices have Nullity at Most Two, Linear Algebra and its Applications, 375 1-11.
  * [20] Horn, R & Johnson, C. (1985) Matrix Analysis, Cambridge University Press, England.
  * [21] Hogben, L. (2009)Minimum Rank Problems, Linear Algebra and its Applications, 432 1961-1974.
  * [22] Hogben, L.(2008) Orthogonal Representations, Minimum Rank, and Graph Complements, Linear Algebra and its Applications, 428 2560-2568.
  * [23] Jiang, Y. et al. (2008) Unitary Matrix Digraphs and Minimum Semidefinite Rank, Linear Algebra and its Applications, 428 1685-1695.
  * [24] Mitchell L.(2011) On the Graph Complement Conjecture for Minimum Semidefinite Rank, Linear Algebra and its Applications, in press, doi:10.1016/j.laa.2011.03.011.
  * [25] Mitchell, L. et al. (2010) Lower Bounds in Minimum Rank Problems, Linear Algebra and its Applications, 432 430-440.
  * [26] Narayan, S. & Sharawi, Y. (2014)Bounds on Minimum Semidefinite Rank of Graphs, Linear and Multilinear Algebra (2014). Retrieved from
http://dx.doi.org/10.1080/03081087.2014.898763 on June 13, 2014.

  * [27] Nylen, P.(1996)Minimum-Rank Matrices with Prescribed Graph, Linear Algebra and its Applications, 248 303-316.
  * [28] Peters, T. (2012) Positive Semidefinite Maximum Nullity and Zero Forcing Number, Electronic Journal of Linear Algebra,23 828-829.
  * [29] Read,R & Wilson, R.(1998) _An Atlas of Graphs_ , Oxford University Press. 125-305.
  * [30] Sharawi, Y ,(2011) Minimum Semidefinite Rank of a Graph.Ph.D. Dissertation. Central Michigan University, Michigan.
  * [31] West,D. B.(1996) _Introduction to Graph Theory_ , Prentice Hall Inc.,.