# Graphs That Are Minor Minimal with Respect to Dimension

Thomas Giardina and Joel Foisy

###### Abstract.

Erdős, Harary, and Tutte defined the dimension of a graph $G$ as the smallest
natural number $n$ such that $G$ can be embedded in $\mathbb{R}^{n}$ with each
edge a straight line segment of length 1. Since the proposal of this
definition, little has been published on how to compute the exact dimension of
graphs and almost nothing has been published on graphs that are minor minimal
with respect to dimension. This paper develops both of these areas. In
particular, it (1) establishes certain conditions under which computing the
dimension of graph sums is easy and (2) constructs three infinitely-large
classes of graphs that are minor minimal with respect to their dimension.

Keywords: embedded graph, graph dimension.
2010 Mathematics Subject Classification. 05C10, 05C83.

##  1\. Introduction

This paper plays a role in the completion of two goals, both having to do with
the classification of graphs. Letting “dimension” mean dimension as defined in
[2], the first goal is to classify all graphs of any given dimension by
constructing a complete list of minimal forbidden minors. The three classes of
minor minimal graphs presented in this paper provide a partial list of minimal
forbidden minors for each dimension.

The second goal is to find an intuitive geometric notion of dimension that is
equivalent to the Colin de Verdière graph invariant, $\mu(G)$ [1].
Unfortunately, Erdős et al’s dimension is not equivalent to $\mu$. However, we
hope that the examples and techniques developed in this paper, combined with
previously published results that tie $\mu(G)$ to $G$’s geometric properties
(see Table 1), will help lead to a definition of dimension that is equivalent
to the Colin de Verdière invariant.

$\mu(G)$ | Geometric Property
---|---
$\leq 0$ |  $G$ has no edges [3]
$\leq 1$ |  $G$ is the disjoint union of paths [4]
$\leq 2$ |  $G$ is outer-planar [3]
$\leq 3$ |  $G$ is planar [3]
$\leq 4$ |  $G$ is linklessly embeddable [6]
Table 1. Known relations between $\mu(G)$ and $G$’s geometric properties.

More specifically, Erdős et al defined the _dimension_ of a graph, denoted
$\dim G$, to be the smallest natural number $n$ such that $G$ can be embedded
in $\mathbb{R}^{n}$ with edges length 1 and vertices mapped to distinct points
(edges are allowed to cross one another but not allowed to cross vertices)
[2]. Here, we show how to calculate the dimension of the sum of graphs and
provide three classes of graphs that are minor minimal with respect to
dimension (or in other words, that are minimal forbidden minors for dimension
$dim(G)-1$).

Integral to both of these efforts is a new notion of dimension, _spherical
dimension_. The spherical dimension of $G$, denoted $\operatorname{s-dim}G$,
is defined similarly to the dimension of $G$, save that the vertices must lie
on an n-dimensional sphere (where two points is a 1-dimensional sphere, a
circle is a 2-dimensional sphere, and so on). By definition, $\dim
G\leq\operatorname{s-dim}G$. We will see later on that every graph has both a
dimension and a spherical dimension (4.7).

Throughout, we will use $\circ_{<}^{[}n]$ to mean “n-dimensional sphere of
radius less than 1.”

The main result with respect to the sum of graphs is:

3.5:

Let $|G|,|H|>1$. If $G$ and $H$ can be embedded on a
$\circ_{<}^{[}\operatorname{s-dim}G]$ and
$\circ_{<}^{[}\operatorname{s-dim}H]$ such that the squares of the radii sum
to 1,

$\dim(G+H)=\operatorname{s-dim}G+\operatorname{s-dim}H.$

Otherwise,

$\dim(G+H)>\operatorname{s-dim}G+\operatorname{s-dim}H.$

Given a graph $\sum_{i=0}^{n}G_{i}$, this theorem often allow us to easily
compute $\dim\sum_{i=0}^{n}G_{i}$ so long as we have a strong understanding of
each $G_{i}$. This allows us to compute the dimension of large, high-
dimensional graphs by through investigating relatively low-dimensional graphs.

Indeed, this technique allow us to construct the following three classes of
minor minimal graphs. Let $\epsilon_{n}$ be the graph with $n$ vertices and no
edges and let

$S_{1}=\epsilon_{1}$

$S_{2}=\epsilon_{2}$

$S_{3}=\epsilon_{3}$

$S_{4}=K_{1}+\epsilon_{3}$

…

$S_{n}=K_{n-3}+\epsilon_{3}$.

Then,

4.6:

$K_{n}$ is minor minimal with respect to dimension $n-1$.

6.2:

$S_{n}+\epsilon_{3}$ is minor minimal with respect to dimension $n+1$.

7.9:

For $1<n<5$, $S_{n}+C_{6}$ is minor minimal with respect to dimension $n+2$,
and for $n\geq 5$, $S_{n}+C_{5}$ is minor minimal with respect to dimension
$n+2$.

Additionally, we find that

5.1, 6.2:

$S_{n}$ is minor minimal with respect to spherical dimension $n-1$.

In the final section, we consider a definition of dimension where edges are
not allowed to cross. Most of the proofs in the previous sections still hold
using this new definition, and using it will allow us to expand the
$S_{n}+C_{6}$ class of minor minimal graphs as follows: Let

$\mathcal{P}_{n}=\left\\{P\;|\;\begin{aligned} &\text{$P$ has $n$ edges, and
each vertex of $P$}\\\ &\text{ is incident to either one or two
edges}\end{aligned}\right\\}$

and

$\mathcal{F}_{n}^{G}=\\{G+P\;|\;P\in\mathcal{P}_{n}\\}.$

Then,

7.3:

The following graphs are minor minimal:

  * •:

$\mathcal{F}_{6}^{S_{1}}-\\{K_{1}+C_{6}\\}$ with respect to dimension 3,

  * •:

$\mathcal{F}_{6}^{S_{n}}$ ($1<n<5$) with respect to dimension $n+2$,

  * •:

$\mathcal{F}_{5}^{S_{n}}$ ($n\geq 5$) with respect to dimension $n+2$.

##  2\. Definitions

We have already seen the two most important definitions, those of dimension
and spherical dimension. When considering these definitions, keep in mind that
we consider a 1-dimensional sphere to be 2 points, a 2-dimensional sphere to
be a circle, and so on. We go against the practice of a 1-sphere being a
circle, a 2-sphere being a sphere, and so on, because we wish to emphasize the
dimension of the space the object sits in rather than the dimension of the
object.

We also saw the phrase “the sum of graphs” in the introduction. The _sum of
two graphs_ $G$ and $H$, denoted $G+H$, is the graph obtained by taking
disjoint copies of $G$ and $H$ and adding all possible edges between $G$ and
$H$. The sum of more than two graph, $G_{1}$, $G_{2}$, …, $G_{n}$, is defined
iteratively: $(((G_{1}+G_{2})+G_{3})+...+G_{n})$.

A minor of a graph is another important notion. A _minor_ $H$ of a graph $G$
is a graph that can be obtained by iteratively applying the following three
operations to $G$:

Vertex Removal:

Remove a vertex from $G$.

Edge Removal:

Remove an edge from $G$.

Edge Contraction:

Merge two adjacent vertices so that the new vertex is adjacent to every vertex
to which either one of the initial two vertices were adjacent.

A graph $G$ is _minor minimal_ with respect to some property if $G$ has the
property but none of its proper minors do. In this paper, we are interested in
graphs that are minor minimal with respect to some dimension – i.e., $G$ has
some dimension $n$, but all of its proper minors have dimension strictly less
than $n$.

For the sake of space, we will also use the following notation:

$|G|$:

The number of vertices of $G$.

$G\cupdot H$:

The disjoint union of $G$ and $H$.

$\epsilon_{n}$:

The empty graph on $n$ vertices.

$C_{n}$:

The cycle graph on $n$ vertices.

$K_{n}$:

The complete graph on $n$ vertices.

$H\subseteq G$:

$H$ is a (not necessarily proper) subgraph of $G$.

$\circ_{<}^{[}n]$:

An n-dimensional sphere of radius less than 1.

We will sometimes use $\circ_{<}^{[}]$ when we want to discuss a hyper sphere
of radius less than 1 and undeclared dimension.

##  3\. Computing the Dimension of Graphs: The General Wheel Graph

Figure 1. A convex hexagon, star hexagon, and $W_{6}$, respectively. Notice
that the convex hexagon is an embedding of $C_{6}$ but the star hexagon is
not.

For $n\geq 3$, let $C_{n}$ denote the cycle graph of length $n$. It is easy to
see that $\dim C_{n}=2$. A slightly more complicated example is the wheel
graph. Define the _wheel graph of length n_ , denoted $W_{n}$, by
$W_{n}=C_{n}+vertex$. Since $C_{n}$ is a subgraph of $W_{n}$,

$\dim W_{n}\geq\dim C_{n}=2.$

But can we embed $W_{n}$ in $\mathbb{R}^{2}$? Suppose we could. Since all the
vertices of $C_{n}$ must be a distance 1 away from $W_{n}$’s central vertex,
$C_{n}$ must lie on a unit circle. It follows that $C_{n}$ must be embedded as
a regular polygon (either convex or star). However, not all regular n-gons are
embeddings of $C_{n}$. For example the star hexagon in Figure 1 is not. We
call such n-gons _degenerate_. The circum-radius of regular, non-degenerate
n-gons is given by

$r=\frac{\sin\left(\frac{n-2m}{n}\pi\right)}{\sin\left(\frac{2m}{n}\pi\right)},$

where $m-1$ vertices are skipped when constructing the n-gon[2]. For example,
in Figure 1, the convex hexagon has $n=6$ and $m=1$ and the star hexagon has
$n=6$ and $m=2$ (although, this star hexagon is also degenerate, so the
equation does not apply). From this equation we get the following radii:

Radii of Non-Degenerate n-gon | $m>\frac{1}{6}n$ | $m=\frac{1}{6}n$ | $m<\frac{1}{6}n$
---|---|---|---
radius | $<1$ | 1 | $>1$
Table 2. The radii of non-degenerate n-gons given $n$ and $m$, the number of
vertices skipped by each edge.

If $\gcd(n,m)\neq 1$, the n-gon is degenerate, so from the above table, we
conclude that no non-degenerate star n-gon has radius 1, and so $C_{6}$ is the
only cyclic graph with an embedding on a unit circle (where the embedding is
as a convex hexagon). Therefore, $\dim W_{6}=2$, and $W_{n}>2$ for all other
$n$.

We now see that all $W_{n}$ can be embedded in $\mathbb{R}^{3}$. Similarly to
in $\mathbb{R}^{2}$, $W_{n}$ can be embedded if and only if all the vertices
of $C_{n}$ can be embedded on a unit sphere. For $3\leq n<6$, such an
embedding is easy; simply place $C_{n}$ on one of the unit sphere’s
appropriately-sized lesser circles, as in Figure 3.

Figure 2. An embedding of $W_{4}$ in $\mathbb{R}^{3}$

For $n\geq 6$, construct the embedding as follows:

Figure 3. The construction of $W_{8}$ embedded in the unit sphere.

  * •

Embed $C_{6}$ on a great circle of $S$.

  * •

Set two adjacent vertices of $C_{6}$, $v$ and $u$, and remove their shared
edge.

  * •

Place the remaining necessary vertices on $S$ as in Figure 3, and connect them
appropriately.

We have thus seen that $W_{n}$ can always be embedded in $\mathbb{R}^{3}$.
Therefore, $\dim W_{6}=2$, and $\dim W_{n}=3$ for all $n\neq 6$.

Let us add another wrinkle. Define the _$k^{th}$ degree wheel graph of length
n_, denoted $W_{n}^{k}$, by $W_{n}^{k}=C_{n}+\epsilon_{k}$. We have already
computed the dimensions of $W_{n}^{1}$, but what about $\dim W_{n}^{2}$, $\dim
W_{n}^{3}$, $\dim W_{n}^{k}$? When computing the dimension of $W_{n}$, we
relied on the fact that $C_{n}$ must lie on a unit circle/sphere in
$\mathbb{R}^{2}$/$\mathbb{R}^{3}$, respectively. But consider $W_{4}^{2}$. In
the incomplete embedding shown in Figure 4, $C_{4}$ must be embedded on a
circle of radius less than 1, not a unit circle.

Figure 4. The 4-cycle embedded with its vertices a distance 1 away from both
the red and blue vertices. The red and blue spheres are the points a distance
1 away from the red and blue vertices, respectively. The orange circle are the
points a distance 1 away from both the red and blue vertex.

This turns out to be a common requirement and is precisely why spherical
dimension is useful. Recall that the spherical dimension of $G$, denoted
$\operatorname{s-dim}G$, is the smallest $n$ such that $G$ can be embedded in
$\mathbb{R}^{n}$ with edges length 1 and vertices mapped to distinct points on
an n-dimensional sphere of radius less than 1. (We define the spherical
dimension of the null graph to be $-\infty$ and the spherical dimension of a
vertex is defined to be 0.) Now that we have the concept of spherical
dimension, we can state and prove three propositions (3.2, 3.3, 3.5) that
greatly simplify computing the dimension of the sum of two graphs.

######  Lemma 3.1.

Let $S$ and $S^{\prime}$ be two n-dimensional spheres with distinct centers
and with radii $r$ and $q$, respectively. The intersection of $S$ and
$S^{\prime}$ either is empty, contains a single point, or is an
(n-1)-dimensional sphere. If the intersection is an (n-1)-dimensional sphere,
say $S^{\prime\prime}$, then $S^{\prime\prime}$ has the following properties:

(i) The radius of $S^{\prime\prime}$ is less than or equal to $r$ and $q$.

(ii) If $r=q$, the radius of $S^{\prime\prime}$ is strictly less than $r=q$.

(iii) If the center of $S$ lies on the surface of $S^{\prime}$, the radius of
$S^{\prime\prime}$ is strictly less than $r$.

###### Proof.

Let $d$ be the distance between the centers of $S$ and $S^{\prime}$. Without
loss of generality, we may place the center of $S$ at the origin and the
center of $S^{\prime}$ at $(d,0,...,0)$. Therefore,

$S=\left\\{(x_{1},...,x_{n})\text{ }|\text{
}x_{1}^{2}+...x_{n}^{2}=r^{2}\right\\}$

and

$S^{\prime}=\left\\{(x_{1},...,x_{n})\text{ }|\text{
}(x_{1}-d)^{2}+...+x_{n}^{2}=q^{2}\right\\}.$

Subtracting $x_{1}^{2}+...x_{n}^{2}=r^{2}$ from
$(x_{1}-d)^{2}+...+x_{n}^{2}=q^{2}$ yields a linear equation in $x_{1}$ alone.
Solving this linear equation yields

$x_{1}=A$

for some constant $A$. Plugging back into the first equation yields

$x_{2}^{2}+x_{3}^{2}+...+x_{n}^{2}=R,$

where

$R=r^{2}-\left(\frac{r^{2}-q^{2}+d^{2}}{2d}\right)^{2}.$

Therefore,

$S\cap S^{\prime}=\\{(x_{1},...,x_{n})\text{ }|\text{ }x_{1}=A,\text{
}x_{2}^{2}+x_{3}^{2}+...+x_{n}^{2}=R\\}$

If $R<0$, no real $x_{2},...,x_{n}$ satisfy
$x_{2}^{2}+x_{3}^{2}+...+x_{n}^{2}=R$, so the intersection is empty. If $R=0$,
$x_{1}=A$ and $x_{2}=x_{3}=...=x_{n}=0$ is the only solution to the previous
equation, so the intersection is a point. Finally, if $R>0$, the set $S\cap
S^{\prime}$ defines an (n-1)-dimensional sphere.

Suppose the last case hold – i.e., $S\cap S^{\prime}$ is an (n-1)-dimensional
sphere, $S^{\prime\prime}$. We now prove that $S^{\prime\prime}$ has the three
desired properties.

(i) All the points of $S^{\prime\prime}$ are a distance $r$ away from the
center of $S$ and a distance $q$ away from the center of $S^{\prime}$. Since
the center of $S^{\prime\prime}$ is the closest point equidistant from all the
points of $S^{\prime\prime}$, it must be at least as close as the centers of
$S$ and $S^{\prime}$. In other words, $S^{\prime\prime}$ must have radius less
than or equal to both $r$ and $q$.

(ii) If $r=q$, $R=r^{2}-\frac{d^{2}}{4}<r^{2}=q^{2}$, so $0<R<r^{2}$. Since
the radius of $S^{\prime\prime}$ is $\sqrt{R}$, $S^{\prime\prime}$ has radius
less than $r=q$.

(iii) If the center of $S$ lies on the surface of $S^{\prime}$, $d=q$. Thus,
$R=r^{2}-\frac{r^{4}}{4q^{2}}$, so $0<R<r^{2}$, and so $S^{\prime\prime}$ has
radius less than $r$.

We have now shown the three desired properties of $S^{\prime\prime}$, and so
the proof is complete. ∎

######  Proposition 3.2.

Let $|G|,|H|>0$. Set an embedding of $G+H$. If either

  * •

$|H|>1$, or

  * •

$G+H$ lies on an n-dimensional sphere,

then $G$ lies on an $\circ_{<}^{[}m]$.

###### Proof.

If $|G|=1$, the proof is trivial, so suppose $|G|>1$. Set an embedding of
$G+H$ in $\mathbb{R}^{n}$, and let $v$ be a vertex of $H$. Then $G$ lies on an
n-dimensional unit sphere, $S$, centered at $v$. Without loss of generality,
let $v$ be at the origin, so

$S=\\{(x_{1},...,x_{n})\text{ }|\text{ }x_{1}^{2}+...+x_{n}^{2}=1\\}.$

Now suppose that $|H|>1$. Then there exists another vertex of $H$,
$v^{\prime}$, and so $G$ also lies on a unit sphere, $S^{\prime}$, centered at
$v^{\prime}$. Thus, $G$ lies on the intersection of $S$ and $S^{\prime}$, so
by 3.1, $G$ lies on either the empty set, a point, or a unique
(n-1)-dimensional sphere, $S^{\prime\prime}$. Since $|G|>1$, $G$ does not lie
on the empty set or on a point, so $G$ lies on $S^{\prime\prime}$. Since $S$
and $S^{\prime}$ both have radius 1, 3.1(ii) yields that the radius of
$S^{\prime\prime}$ is less than the radius of $S$, which is 1. In other words,
$G$ lies on an $\circ_{<}^{[}n-1]$, as desired.

Now suppose that $G+H$ lies on a hyper-sphere. Then $G+H$ lies on an
n-dimensional sphere, $S^{\prime}$. Therefore, $G+H$ lies on the intersection
of $S$ and $S^{\prime}$, and so 3.1 yields that $G+H$ lies on either the empty
set, a point, or an (n-1)-dimensional sphere, $S^{\prime\prime}$. Since
$|G|>1$, $G$ does not lie on the empty set or on a point, so $G$ lies on
$S^{\prime\prime}$. Since the center of $S$, $v$, is a vertex of $H$, the
center of $S$ lies on the surface of $S^{\prime}$, and so 3.1(iii) yields that
the radius of $S^{\prime\prime}$ is less than the radius of $S$, which is 1.
In other words, $G$ lies on an $\circ_{<}^{[}n-1]$, as desired. ∎

######  Proposition 3.3.

Let $G$ be a graph. Set an embedding of $G$ in $\mathbb{R}^{n+m}$ such that
$G$ is embedded on a unique n-dimensional sphere $S$ with radius $r$. Then the
points a distance $d>r$ away from all the points of $G$ form the unique
m-dimensional sphere $S^{\prime}$ that

  * •

shares the same center as $S$,

  * •

lies in a plan orthogonal to the plane $S$ lies in, and

  * •

has radius $\sqrt{d^{2}-r^{2}}$.

(Note: We will mostly use this result with $r<d=1$.)

###### Proof.

Set an embedding of $G$ in $\mathbb{R}^{n+m}$ such that $G$ is embedded on a
unique n-dimensional sphere of radius $r$, $S$. Without loss of generality,
let

$S=\left\\{(x_{1},...,x_{n+m})\text{ }|\text{
}x_{1}^{2}+...x_{n}^{2}=r^{2},\text{ }x_{n+1}=...=x_{m}=0\right\\}.$

Now, let $p=(p_{1},...,p_{n+m})$ be a point a distance $d$ away from every
vertex of $G$, and let $p_{proj}=(p_{1},...,p_{n},0,...,0)$. For every vertex
$v$ of $G$,

$|p_{proj}-v|=\sqrt{d^{2}-p_{n+1}^{2}-...-p_{n+m}^{2}}.$

In other words, putting

$q=\sqrt{d^{2}-p_{n+1}^{2}-...-p_{n+m}^{2}},$

we have that the vertices of $G$ must lie on an $\circ_{<}^{[}n]$ of radius
$q$ centered at $p_{proj}$.

Of course, the points of $G$ are also on $S$. Therefore, the points of $G$
must lie on the intersection of two $\circ_{<}^{[}n]$s. By choice of
embedding, $G$ cannot be embedded on an $\circ_{<}^{[}n-1]$ (and clearly
cannot be embedded on a set of one point or the empty set), so 3.1 yields that
$p_{proj}$ must be the center of $S$, which is the origin. Since $p_{proj}$
lies on the origin, $p$ must be of the form $(0,...,0,p_{n+1},...,p_{n+m})$.

Now, let $v=(v_{1},...,v_{n},0,...,0)$ be a vertex of $G$. The Euclidean
distance between $p$ and $v$ is

$d=\sqrt{v_{1}^{2}+...+v_{n}^{2}+p_{n+1}^{2}+...+p_{n+m}^{2}}.$

Since $v_{1}^{2}+...+v_{n}^{2}=r^{2}$, this equation can be rewritten as

$p_{n+1}^{2}+...+p_{n+m}^{2}=d^{2}-r^{2},$

so the set of points a distance $d$ away from all the vertices of $G$ are

$\left\\{(x_{1},...,x_{n})\text{ }|\text{
}x_{1}=...=x_{n}=0,x_{n+1}^{2}+...x_{m}^{2}=d^{2}-r^{2}\right\\}.$

Since $d>r$, $d^{2}-r^{2}>0$, and so the above set defines an
$\circ_{<}^{[}m]$. Indeed, this $\circ_{<}^{[}m]$ has the same center as $S$
(the origin) and is orthogonal to $S$, as desired. ∎

######  Theorem 3.4.

Let $|G|,|H|>1$. Then the following two statements hold:

Suppose that $G$ and $H$ can be embedded on a $\circ_{<}^{[}n_{1}]$ and
$\circ_{<}^{[}n_{2}]$, respectively, such that the squares of the radii sum to
1. Then $G+H$ can be embedded in $\mathbb{R}^{n_{1}+n_{2}}$.

Conversely, if $G+H$ can be embedded in $\mathbb{R}^{n}$, there exists $n_{1}$
and $n_{2}$ such that $n_{1}+n_{2}=n$ and $G$ and $H$ can be embedded on an
$\circ_{<}^{[}n_{1}]$ and $\circ_{<}^{[}n_{2}]$, respectively, such that the
squares of the radii sum to 1.

###### Proof.

Suppose that $G$ and $H$ can be embedded in $\circ_{<}^{[}n_{1}]$ and
$\circ_{<}^{[}n_{2}]$ as in the statement. Let $r_{1}$ be the radius of
$\circ_{<}^{[}n_{1}]$ and $r_{2}$ be the radius of $\circ_{<}^{[}n_{2}]$. Then
embedding $G$ on the $\circ_{<}^{[}n_{1}]$ defined by

$\left\\{(x_{1},...,x_{n_{1}+n_{2}})\mid
x_{1}^{2}+...+x_{n_{1}}^{2}=r_{1}^{2},x_{n_{1}+1}=...=x_{n_{1}+n_{2}}=0\right\\},$

$H$ on the $\circ_{<}^{[}n_{2}]$ defined by

$\left\\{(x_{1},...,x_{n_{1}+n_{2}})\mid
x_{1}=...=x_{n_{1}}=0,x_{n_{1}+1}^{2}+...+x_{n_{1}+n_{2}}^{2}=r_{2}^{2}\right\\},$

and adding all possible edges between $G$ and $H$ yields an embedding of
$G+H$.

Now suppose that $G+H$ can be embedded in $\mathbb{R}^{n}$. By 3.2, $G$ lies
on a $\circ_{<}^{[}]$. Choose the unique lowest-dimensional such
$\circ_{<}^{[}]$. Let its dimension be $n_{1}$ and its radius be $r_{1}$. Then
by 3.3, $H$ lies on an $\circ_{<}^{[}n-n_{1}]$ with radius
$\sqrt{1-r_{1}^{2}}$. Setting $n_{2}=n-n_{1}$ completes the proof. ∎

######  Corollary 3.5.

Let $|G|,|H|>1$. If $G$ and $H$ can be embedded on a
$\circ_{<}^{[}\operatorname{s-dim}G]$ and
$\circ_{<}^{[}\operatorname{s-dim}H]$ such that the squares of the radii sum
to 1,

$\dim(G+H)=\operatorname{s-dim}G+\operatorname{s-dim}H.$

Otherwise,

$\dim(G+H)>\operatorname{s-dim}G+\operatorname{s-dim}H.$

###### Proof.

This follows easily of 3.4. ∎

Now that we have 3.5, computing $\dim W_{n}^{k}$ reduces to computing the
spherical dimension of $C_{n}$.

######  Lemma 3.6.

For $n\neq 6$, $\operatorname{s-dim}C_{n}=2$, but
$\operatorname{s-dim}C_{6}=3$.

###### Proof.

Given Table 2, showing that $\operatorname{s-dim}C_{n}=2$ is equivalent to
showing that there exists an $m$ such that $m\nmid n$ and
$\frac{1}{6}n<m<\frac{1}{2}n$. For $n<6$, $m=1$ works. For $n=6$, clearly no
$m$ exists, but by methods similar to those in Figure 3, $C_{6}$ can be
embedded on a $\circ_{<}^{[}3]$.

To complete the proof, we must show that such an $m$ exists for $n>6$. Set
$n>6$. There exists an $m^{\prime}$ such that
$\frac{1}{6}n<m^{\prime}<m^{\prime}+1<\frac{1}{2}n$. If they both divide $n$,
then $m^{\prime}(m^{\prime}+1)$ divides $n$ because consecutive integers are
relatively prime. Since $\frac{1}{6}n<m^{\prime}$, we conclude
$(m^{\prime}+1)<6$. We now complete the proof by checking the cases
$m^{\prime}=1,...,4$:

  * •

If $m^{\prime}=1$, $m^{\prime}<1<\frac{1}{6}n$, so we are done.

  * •

If $m^{\prime}=2$, $m^{\prime}>\frac{1}{6}n$, and
$m^{\prime}(m^{\prime}+1)\mid n$, then $n=6$, so we are done.

  * •

If $m^{\prime}=3$, $m^{\prime}>\frac{1}{6}n$, and
$m^{\prime}(m^{\prime}+1)\mid n$, then $n=12$. But $m=5$ works, so we are
done.

  * •

If $m^{\prime}=4$, $m^{\prime}>\frac{1}{6}n$, and
$m^{\prime}(m^{\prime}+1)\mid n$, then $n=20$. But $m=6$ works, so we are
done.

Thus, the desired $m$ exists for every $n>6$, and so
$\operatorname{s-dim}C_{n}=2$ for all $n>6$. ∎

######  Corollary 3.7.

The dimensions of the wheel graphs are as follows:

Dimension of $W_{n}^{k}$ | $n=6$ | $n\neq 6$
---|---|---
$k=1$ | 2 | 3
$k=2$ | 4 | 3
$k\geq 3$ | 5 | 4

###### Proof.

We already proved the result for $k=1$, so we consider only the cases for
$k\geq 2$. Notice that $\epsilon_{2}$ can be embedded on a $\circ_{<}^{[}1]$
of any radius and that for $j>2$, $\epsilon_{j}$ can be embedded on a
$\circ_{<}^{[}2]$ of any radius. The result now follows from 3.6 and 3.5. ∎

##  4\. Finding Graphs Minor Minimal with Respect to Dimension: $K_{n}$

Once we have computed the dimension of a graph, $G$, we might begin wondering
about the dimensions of its minors. This topic is not as simple as it first
appears. For example, unlike subgraphs, minors sometimes have greater
dimension than the original graph. Indeed, an example we worked with in the
previous section illustrate this point: $W_{5}$ is a minor of $W_{6}$, but

$\dim W_{5}=3>2=\dim W_{6}.$

In this section, we restrict our focus to whether a graph $G$ is minor minimal
with respect to dimension. Recall that $G$ is minor minimal with respect to
dimension if every proper minor of $G$ has dimension less than $G$.

For example, consider $K_{3}$. Since $K_{3}$ has dimension 2 and all of its
minors have dimension at most 1, $K_{3}$ is minor minimal with respect to
dimension 2.

It turns out that $K_{n}$ ($n\geq 3$) is minor minimal with respect to
dimension $n-1$. To understand why, we must first explore some other special
properties of $K_{n}$. In particular, notice that $K_{3}$’s embedding is
“unique” and “compact.” More precisely, every embedding of $K_{3}$ is a
triangle, and the vertices of $K_{3}$ lie on a circle of radius less than
$\frac{\sqrt{2}}{2}$. The following proposition shows that these two
properties are very useful:

######  Proposition 4.1.

Set an embedding of $G$ such that $G$ lies on a unique $\circ_{<}^{[}n]$,
which has radius $r$. Place a vertex a distance 1 away from all the vertices
of $G$ (which is possible by 3.3) and adjoin it to $G$. The result is an
embedding of $G+vertex$ which lies uniquely on an (n+1)-dimensional sphere of
radius $R=\frac{1}{2\sqrt{1-r^{2}}}$.

###### Proof.

Set an embedding of $G$ such that $G$ is embedded on a unique
$\circ_{<}^{[}n]$, $S$, which has radius $r$. Without loss of generality, let

$S=\left\\{(x_{1},...,x_{n+m}\;|\;x_{1}^{2}+...+x_{n}^{2}=r^{2}\text{ and
}x_{n+1}=...=x_{n+m}=0\right\\}.$

From 3.3, we know that one of the points a distance 1 away from $S$ is the
point defined by $x_{n+1}=\sqrt{1-r^{2}}$ and all other $x_{i}=0$. Call this
point $p_{v}$. Without loss of generality, we construct $G+vertex$ by placing
a vertex, $v$, on $p_{v}$ and adjoining $v$ to $G$.

We must now show that $G+vertex$ lies on a unique (n+1)-dimensional sphere,
$S^{\prime}$, which has radius $R=\frac{1}{2\sqrt{1-r^{2}}}$. Consider a
potential center of $S^{\prime}$, $p$. 3.3 guarantees that the points
equidistant from $G$ must lie in the last $m$ coordinates, so $p$ is of the
form $(0,...,0,x_{n+1},...,x_{n+m})$. Moreover, $p$ must be of the form
$(x_{1},...,x_{n+1},0,...,0)$ if $S^{\prime}$ is to both be $n+1$ dimensional
and contain $p_{v}$ and $S$. Therefore, $p=(0,...,0,p_{n+1},0,...,0)$ for some
real number $p_{n+1}$.

Letting $p_{S}$ be any point on $S$, we have

$|p-p_{S}|=\sqrt{r^{2}+p_{n+1}^{2}}$

and

$|p-p_{v}|=\sqrt{1-r^{2}}-p_{n+1}.$

For $p$ to be the center of $S$, $p$ must be equidistant from both $p_{v}$ and
$p_{S}$, so the two expressions must be equal. Solving this equality yields

$p_{n+1}=\frac{1-2r^{2}}{2\sqrt{1-r^{2}}}.$

Plugging back into $\left|p-p_{v}\right|$ yields the radius of $S^{\prime}$,
$\frac{1}{2\sqrt{1-r^{2}}}$, as desired. Since $S$ has uniquely defined both
the center and radius of $S^{\prime}$, it has uniquely defined $S^{\prime}$,
and so we’re done. ∎

######  Corollary 4.2.

Set an embedding such that $G$ lies on a unique $\circ_{<}^{[}n]$ of radius
$r$. Adjoin a vertex, $v$, and let $R$ be the radius of the unique
(n+1)-dimensional sphere on which $G+v$ lies (as guaranteed by 4.1).

a. If $r<\frac{\sqrt{2}}{2}$, $r<R<\frac{\sqrt{2}}{2}$.

b. If $r=\frac{\sqrt{2}}{2}$, so does $R$.

c. If $r>\frac{\sqrt{2}}{2}$, $R-r>0$ and increases as $r$ increases.

###### Proof.

Figure 5 shows that $r<R$ if $r\neq\frac{\sqrt{2}}{2}$ and $r=R$ if
$r=\frac{\sqrt{2}}{2}$. It should also be obvious from Figure 5 that $R-r$
increases as $r$ increases if $r>\frac{\sqrt{2}}{2}$ ($R$ will be bigger and
the n-dimensional sphere will be farther above the center of (n+1)-dimensional
sphere). Figure 6 shows that $R<\frac{\sqrt{2}}{2}$ if $r<\frac{\sqrt{2}}{2}$.
∎

Figure 5. The (n+1) and n-dimensional sphere projected into two dimensions
(the circle and the thick line, respectively). If the n-dimensional sphere had
radius greater than, equal to, or less than $\frac{\sqrt{2}}{2}$, it lies
above, at, below the center of the (n+1)-dimensional sphere, respectively.
Figure 6. If the n-dimensional sphere lies below the center of the
(n+1)-dimensional sphere, $\alpha>\frac{\pi}{2}$. Therefore, the right
triangle constructed from $v$ and two radii has hypotenuse less than 1, so the
radius of the (n+1)-dimensional sphere is less than $\frac{\sqrt{2}}{2}$.

Since $K_{3}$ has a unique embedding, 4.1 yields a unique embedding of
$K_{4}$. Since $K_{3}$’s unique embedding is on a circle of radius less than
$\frac{\sqrt{2}}{2}$, 4.2 shows that $K_{4}$’s unique embedding is as well.
And so on.

######  Proposition 4.3.

The graph $K_{n}$ has a unique embedding. In this embedding, $K_{n}$ lies on a
unique $\circ_{<}^{[}n-1]$, which has radius less than $\frac{\sqrt{2}}{2}$.

###### Proof.

We proceed by induction. We have already seen the case when $n=3$. For some
$n\geq 3$, suppose $K_{n}$ has a unique embedding in which $K_{n}$ lies on an
$\circ_{<}^{[}n-1]$ of radius $r<\frac{\sqrt{2}}{2}$ in this embedding. Set an
embedding of $K_{n+1}$. Remove a vertex, $v$, from $K_{n+1}$ to get $K_{n}$.
$K_{n}$ lies on an $\circ_{<}^{[}n-1]$ of radius $r$. Adding back $v$, 4.2
yields that $K_{n+1}$ lies on a unique $\circ_{<}^{[}n]$, which has radius
less than $\frac{\sqrt{2}}{2}$, as desired. ∎

######  Corollary 4.4.

The graph $K_{n}$ has dimension and spherical dimension $n-1$.

###### Proof.

This is a direct consequence of 4.3 ∎

We have now completed the first step of showing that $K_{n}$ is minor minimal,
computing the dimension of $K_{n}$. We must now complete the second step,
showing that every proper minor of $K_{n}$ has lesser dimension:

######  Lemma 4.5.

Let $H$ be a minor of $K_{n}$ (denoted $H\prec K_{n}$). Then $\dim H<n-1$.

###### Proof.

We proceed by induction. We have already completed the base case. Assume every
minor of $K_{n}$ has dimension less than $n-1$. We must show that $\dim H<n$
for every $H\prec K_{n+1}$. To do this, we consider two exhaustive cases:

$H$ is obtained by removing at least one vertex or contracting at least one
edge:

Then $|H|\leq n$, so $H$ is a subgraph of $K_{n}$, and so $\dim H\leq\dim
K_{n}=n-1<n$, as desired.

$H$ is obtained by only removing edges:

It suffices to show that $\dim K_{n+1}-edge<n$, so consider $K_{n+1}-edge$.
Label the two vertices incident to the removed edge $v_{1}$ and $v_{2}$, and
remove them both. The resulting subgraph of $K_{n+1}-edge$ is $K_{n-1}$, so
4.3 yields that it lies on an $\circ_{<}^{[}n-2]$. Therefore, by 3.3, there
are two points a distance 1 from all the vertices of $K_{n-1}$ in
$\mathbb{R}^{n-1}$. Placing $v_{1}$ and $v_{2}$ on these points and adjoining
them to $K_{n-1}$ results in an embedding of $K_{n+1}-edge$ in
$\mathbb{R}^{n-1}$. Thus, $\dim K_{n+1}-edge\leq n-1<n$, as desired.

Therefore, regardless of how the minor $H\prec K_{n+1}$ is derived, $\dim
H<n$. This completes the proof by induction. ∎

All together:

######  Theorem 4.6.

The graph $K_{n}$ is minor minimal with respect to dimension $n-1$.

###### Proof.

This is a direct consequence of 4.3 and 4.5. ∎

Our work with $K_{n}$ now allows us to prove a few important (albeit,
peripheral) facts:

######  Theorem 4.7.

Every graph has both a dimension and a spherical dimension.

###### Proof.

Let $G$ be a graph with at least two vertices. $G$ is a subgraph of $K_{n}$
for some $n$. Therefore, $G$ can be embedded in $\mathbb{R}^{n-1}$. There
exists some $1\leq m\leq n-1$ such that $G$ can be embedded in
$\mathbb{R}^{m}$ but not $\mathbb{R}^{m-1}$; $\dim G=m$.

That $G$ has a spherical dimension follows identically. ∎

######  Proposition 4.8.

For any graph, $G$, $\operatorname{s-dim}(G+vertex)>\operatorname{s-dim}G$.

###### Proof.

This is a direct consequence of 3.2 and 4.1. ∎

It is tempting to also claim that $\dim(G+vertex)>\dim G$ or
$\dim(G+vertex)>\operatorname{s-dim}G$, but this is not generally true. For
example, we have already seen that $\dim C_{6}=2$ and
$\operatorname{s-dim}C_{6}=3$, but $C_{6}+vertex=W_{6}$ has dimension 2.

Another interesting question is whether there exists a graph, $G$, such that
$\operatorname{s-dim}(G+vertex)>\operatorname{s-dim}G+1$. This is an open
question. However, notice that it would suffice to find a $G$ that cannot be
embedded on an $\circ_{<}^{[}\operatorname{s-dim}G]$ of radius less than or
equal to $\frac{\sqrt{2}}{2}$ (to see this, iteratively apply 4.1 to $G$).
This question is briefly revisited at the beginning of Section 7.

##  5\. Finding Graphs Minor Minimal with Respect to Spherical Dimension:
$S_{n}$

We have found a class of graphs that is minor minimal with respect to
dimension. Now let us find a class of graphs that is minor minimal with
respect to spherical dimension. In particular, we will find the graphs with
the fewest number of vertices that are minor minimal with respect to spherical
dimension $n-1$.

Since $\operatorname{s-dim}K_{n-1}=n-2$ and $\operatorname{s-dim}K_{n}=n-1$,
we know such a graph must have $n$ vertices. Let us give these graphs a name:
Let $\mathbb{S}_{n}$ denote the set of graphs that are minor minimal with
respect to spherical dimension $n-1$ and have $n$ vertices, and let $S_{n}$ be
some graph $S_{n}\in\mathbb{S}_{n}$. Computing $\mathbb{S}_{n}$ is relatively
easy for small $n$:

######  Proposition 5.1.

The following are $\mathbb{S}_{n}$ for small $n$:

a. $\mathbb{S}_{1}=\\{\epsilon_{1}\\}$.

b. $\mathbb{S}_{2}=\\{\epsilon_{2}\\}$.

c. $\mathbb{S}_{3}=\\{\epsilon_{3}\\}$.

d. $\mathbb{S}_{4}=\\{K_{3,1}\\}$ (equivalently, $\\{K_{1}+\epsilon_{3}\\}$).

Indeed, $\epsilon_{1}$, $\epsilon_{2}$, and $\epsilon_{3}$ are the only minor
minimal graphs with respect to their respective spherical dimensions.

###### Proof.

a. Recall that $\operatorname{s-dim}\epsilon_{0}=-\infty$ and
$\operatorname{s-dim}\epsilon_{1}=0$. Since the only minor of $\epsilon_{1}$
is the empty graph, $\epsilon_{1}$ is minor minimal with respect to spherical
dimension 0. Moreover, since every graph that is not the empty graph contains
$\epsilon_{1}$ as a subgraph, $\epsilon_{1}$ is the only minor minimal graph
with spherical dimension 0.

b. Since $\epsilon_{2}$ can be embedded on two points but not a single point,
$\operatorname{s-dim}\epsilon_{2}=1$. Since all of $\epsilon_{2}$’s minors are
subgraphs of $\epsilon_{1}$, which we just saw has spherical dimension 0,
$\epsilon_{2}$ is minor minimal with respect to spherical dimension 1.
Moreover, any graph that is not the empty graph or $\epsilon_{1}$ contains
$\epsilon_{2}$ as a subgraph, so $\epsilon_{2}$ is the only minor minimal
graph with respect to spherical dimension 1.

c. Since $\epsilon_{3}$ can be embedded on a circle but not two points,
$\operatorname{s-dim}\epsilon_{3}=2$. Since all of $\epsilon_{3}$’s minors are
subgraphs of $\epsilon_{2}$, which we just saw has spherical dimension 1,
$\epsilon_{3}$ is minor minimal with respect to spherical dimension 2. All
graph with two or fewer vertices, have spherical dimension at most 1, so since
all graph with three or more vertices contain $\epsilon_{3}$ as a subgraph,
$\epsilon_{3}$ is the only minor minimal graph with respect to spherical
dimension 2.

d. Since $\operatorname{s-dim}\epsilon_{3}=2$ and can be embedded on circles
of arbitrarily small radius, 4.1 yields that
$\operatorname{s-dim}K_{1}+\epsilon_{3}=3$. We now show that
$\operatorname{s-dim}H<3$ for all $H\prec K_{3,1}$ by considering two
exhaustive cases:

$H\prec K_{3,1}$ is obtained by removing at least one vertex or contracting at
least one edge:

Then $H\subseteq K_{3}$, and so $\operatorname{s-dim}H\leq 2$.

$H$ is obtained by only removing edges:

Then $H\subseteq P_{3}\cupdot vertex$ (where $P_{3}$ is the path on 3
vertices). Since $\operatorname{s-dim}P_{3}\cupdot vertex=2$,
$\operatorname{s-dim}H\leq 2$.

Since every minor of $K_{3,1}$ falls into one of the two above categories,
every minor of $K_{1}+\epsilon_{3}$ has spherical dimension at most 2, and so
$K_{3,1}$ is minor minimal with respect to spherical dimension 3.

Finally, we show that $K_{3,1}$ is the only member of $\mathbb{S}_{4}$. To do
this, we must show that every subgraph of $K_{4}$ that is not a supergraph of
$K_{3,1}$ has spherical dimension at most 2. The following more general lemma
suffices: ∎

######  Lemma 5.2.

Let $K_{3,1}\subseteq G\subseteq K_{4}$. Every proper minor of $G$ that is not
a supergraph of $K_{3,1}$ can be embedded on a circle of radius less than or
equal to $\frac{\sqrt{2}}{2}$.

###### Proof.

We need to consider the minors of the four graphs listed in Figure 7.

Figure 7. The four graphs that are both subgraphs of $K_{4}$ and supergraphs
of $K_{3,1}$.

Since $K_{3}$ can be embedded on a circle of radius less than
$\frac{\sqrt{2}}{2}$, it suffices to consider only the minors obtained by
removing one edge from any of these four graphs.

Minors of $K_{4}$:

Up to symmetry, every subgraph of $K_{4}$ obtained by removing a single edge
is $K_{4}-edge$, which is a supergraph of $K_{3,1}$ and so considered below.

Minors of $K_{4}-edge$:

Up to symmetry, one can obtain two subgraphs of $K_{4}-edge$ by removing a
single edge: $C_{4}$ and $K_{3,1}+edge$.

$C_{4}$:

Embed $C_{4}$ as a square. All the vertices of $C_{4}$ are a distance
$\frac{\sqrt{2}}{2}$ away from the center of the square, so $C_{4}$ can be
embedded on a $\circ_{<}^{[}2]$ of radius $\frac{\sqrt{2}}{2}$.

$K_{3,1}+edge$:

$K_{3,1}+edge$ is a supergraph of $K_{3,1}$ and so is considered below.

Minors of $K_{3,1}+edge$:

Up to symmetery, one can obtain three different subgraphs of $K_{3,1}+edge$ by
removing a single edge: $P_{4}$, $K_{3}\cupdot vertex$, and $K_{3,1}$.

$P_{4}$:

$P_{4}\subseteq C_{4}$, which we just saw can be embedded on a
$\circ_{<}^{[}2]$ of radius $\frac{\sqrt{2}}{2}$.

$K_{3}\cupdot vertex$:

By 4.3, $K_{3}$ can be embedded on a $\circ_{<}^{[}2]$ of radius less than
$\frac{\sqrt{2}}{2}$. Embed $K_{3}$ on such a $\circ_{<}^{[}2]$ and add
another vertex anywhere on the $\circ_{<}^{[}2]$ that does not already have a
vertex to get an embedding of $K_{3}\cupdot vertex$ on a $\circ_{<}^{[}2]$ of
radius less than $\frac{\sqrt{2}}{2}$.

$K_{3,1}$:

$K_{3,1}$ is, of course, a subgraph of itself, and so we consider it below.

Minors of $K_{3,1}$:

Up to symmetry, the only subgraph is $P_{3}\cupdot vertex$, which is a
subgraph of many of the graphs already considered and so can be embedded on a
$\circ_{<}^{[}2]$ of radius less than $\frac{\sqrt{2}}{2}$.

We have considered all possible minors obtained by removing one edge from one
of the desired graphs, and so we are done. ∎

To prove the general claim $\mathbb{S}_{n}=\\{K_{n-3}+\epsilon_{3}\\}$ for
$n\geq 4$, we need a few more lemmas. For the next lemma, we need the
following definition. Let

$R_{G}=\inf_{S\in\left\\{\begin{subarray}{c}\text{$\circ_{<}^{[}\operatorname{s-dim}G]$s
on which }\\\ \text{ $G$ can be embedded}\end{subarray}\right\\}}\text{radius
of $S$}$

######  Lemma 5.3.

Let $G$ be a graph such that $\operatorname{s-dim}G=2$ and $|G|=4$. Then
$R_{G}\leq\frac{\sqrt{2}}{2}$

###### Proof.

If $G$ is a supergraph of $K_{3,1}$, it has spherical dimension greater than 2
(5.1d). Otherwise, $G$ can be embedded on a circle of radius less than or
equal to $\frac{\sqrt{2}}{2}$ (5.2). This completes the proof. ∎

######  Lemma 5.4.

For $n\geq 4$, $\operatorname{s-dim}(K_{n-3}+\epsilon_{3})=n-1$.

###### Proof.

Since $K_{n-3}+\epsilon_{3}\subseteq K_{n}$,
$\operatorname{s-dim}(K_{n-3}+\epsilon_{3})\leq n-1$. To get the reverse
inequality, we proceed by induction. 5.1d provides the base case. Suppose that
$\operatorname{s-dim}(K_{n-3}+\epsilon_{3})\geq n-1$. Since
$K_{n-2}+\epsilon_{3}=(K_{n-3}+\epsilon_{3})+vertex$, 4.8 yields that
$\operatorname{s-dim}(K_{n-2}+\epsilon_{3})\geq n$, completing the proof. ∎

The next lemma and proof uses the following two definitions:

  * •

A vertex of $G$ is called a _center vertex_ if it is adjacent to every other
vertex of $G$.

  * •

$G+_{?}H$ denotes the set of all graphs that can be constructed from $G\cupdot
H$ by adding some edges (possibly none or all) between $G$ and $H$.

######  Lemma 5.5.

Let $G$ be a graph with $n\geq 4$ vertices. Suppose that $H$ is a subgraph of
$K_{3,1}$ for every subgraph, $H$, of $G$ obtained by only removing vertices
and with $|H|=4$ Then $K_{n-3}+\epsilon_{3}\subseteq G$.

###### Proof.

If $G=K_{n}$, we are done, so suppose $G\neq K_{n}$. Then there exists non-
adjacent vertices $v_{1}$ and $v_{2}$. Let $H$ the graph obtained by removing
all but the following four vertices from $G$: $v_{1}$, $v_{2}$, and some
arbitrary $u_{1}$ and $u_{2}$. Since $K_{3,1}$ is a subgraph of $H$, $H$ has a
center vertex. Since $v_{1}$ and $v_{2}$ are not adjacent to one another,
neither can be center vertices of $H$, so either $u_{1}$ or $u_{2}$ is a
center vertex of $H$. Regardless, $u_{1}$ and $u_{2}$ are adjacent.

Since $u_{1}$ and $u_{2}$ were arbitrary vertices of $G$, not $v_{1}$ or
$v_{2}$, any pair of vertices of $G$ that do not include $v_{1}$ or $v_{2}$
are adjacent. In other words, $G\in K_{n-2}+_{?}\epsilon_{2}$, where
$\epsilon_{2}$’s two vertices are $v_{1}$ and $v_{2}$. To determine which
edges exist between $K_{n-2}$ and $\epsilon_{2}$, we consider two exhaustive
cases:

  * •

Suppose every vertex of $K_{n-2}$ is adjacent to both $v_{1}$ and $v_{2}$.
Then $G=K_{n-2}+\epsilon_{2}$, which is a supergraph of
$K_{n-3}+\epsilon_{3}$, and we are done.

  * •

Suppose there exists at least one vertex, $w$, of $K_{n-2}$ that is not
adjacent to at least one of $v_{1}$ or $v_{2}$. Let $H$ be the graph obtained
by removing all but the following four vertices from $G$: $v_{1}$, $v_{2}$,
$w$, and some arbitrary $u$. Since $v_{1}$ and $v_{2}$ are not adjacent, and
$w$ is not adjacent to at least one of $v_{1}$ and $v_{2}$, $u$ must be the
center vertex of $H$. In other words, $u$ is adjacent to $v_{1}$, $v_{2}$, and
$w$. Since $u$ was arbitrary, every vertex of $G$ not $v_{1}$, $v_{2}$, or $w$
is adjacent to each of $v_{1}$, $v_{2}$, and $w$. Therefore, $G$ is a
supergraph of $K_{n-3}+\epsilon_{3}$, where the $\epsilon_{3}$’s vertices are
$v_{1},v_{2},w$.

Either way, $K_{n-3}+\epsilon_{3}$ is a subgraph of $G$, as desired. ∎

######  Proposition 5.6.

Let $G$ be a graph. There exists some $n\in\mathbb{N}$ such that

$\operatorname{s-dim}(G+K_{n})>\operatorname{s-dim}G+n$

if and only if $R_{G}>\frac{\sqrt{2}}{2}$.

The proof of 5.6 requires many iterative applications of 4.1. To simplify the
proof, we define $R(r)=\frac{1}{2\sqrt{1-r^{2}}}$ and $R^{n}$
($n\in\mathbb{Z}$) as the composition of $R(x)$ $n$ times. $R(x)$ has the
following properties:

######  Lemma 5.7.

Let $0<r,r_{1},r_{2}<1$.

a. For all $n\in\mathbb{Z}^{+}$, $r\leq R^{n}(r)$.

b. For all $n\in\mathbb{Z}^{+}$, if $r_{1}<r_{2}$ and $R^{n-1}(r_{2})<1$,
$R^{n}(r_{1})<R^{n}(r_{2})$.

c. For any $n\in\mathbb{Z}^{+}$, there exists an $r$ such that
$\frac{\sqrt{2}}{2}<r<1$ and $R^{n}(r)<1$.

d. For any $r>\frac{\sqrt{2}}{2}$, there exists an $n$ such that $R^{n}(r)>1$.

e. Let $G$ be a graph, and fix an embedding such that $G$ lies on a unique
$\circ_{<}^{[}m]$, which has radius $r$.

  1. (1)

If $r\leq\frac{\sqrt{2}}{2}$, then for all $i\in\mathbb{Z}^{+}$, $G+K_{i}$
lies on a unique $\circ_{<}^{[}m+i]$, which has radius $R^{i}(r)$.

  2. (2)

Let $r\geq\frac{\sqrt{2}}{2}$, and let $n$ be the smallest positive integer
such that $R^{n}(r)>1$. For all $i\leq n$, $G+K_{i}$ lies on a unique
(n+i)-dimensional sphere, which has radius $R^{i}(r)$. For $i>m$, $G+K_{i}$
cannot be embedded on a q-dimensional sphere for any $q$.

###### Proof.

a. We proceed inductively on $n$. The equation $r=R^{0}(r)$ takes care of the
base case. Suppose that $r<R^{n}(r)$. By 4.2,

$r<R^{n}(r)<R(R^{n}(r))=R^{n+1}(r),$

completing the inductive step and thus the proof.

b. We proceed inductively on $n$. By choice of $r_{1}$ and $r_{2}$,
$R^{0}(r_{1})=r_{1}<r_{2}=R^{0}(r_{2}$). Suppose
$R^{n}(r_{1})<R^{n}(r_{2})<1$. Then

$R^{n+1}(r_{2})=\frac{1}{2\sqrt{1-(R^{n}(r_{2}))^{2}}}>\frac{1}{2\sqrt{1-(R^{n}(r_{1}))^{2}}}=R^{n+1}(r_{1}),$

completing the inductive step and thus the proof.

c. We proceed by induction. The base case is trivial. Suppose there exists an
$r$ such that $\frac{\sqrt{2}}{2}<r<1$ and $R^{n}(r)<1$. We must find an
$r^{\prime}$ such that $R^{n+1}(r^{\prime})<1$. Consider
$r^{\prime}=R^{-1}(r)$. $R^{n+1}(r^{\prime})=R^{n}(r)<1$, and by 4.2,
$\frac{\sqrt{2}}{2}<r^{\prime}<r$. This completes the inductive step and thus
the proof.

d. Put $\delta=R(r)-r$ and choose
$n=\left\lceil\frac{1-r}{\delta}\right\rceil$. By 4.2c,
$R^{i}(r)-R^{i-1}(r)\geq\delta$ for all $i\geq 1$. Therefore,

$R^{n}(r)=r+\sum_{i=1}^{n}\left(R^{i}(r)-R^{i-1}(r)\right)\geq
n\delta+r\geq(1-r)+r=1,$

as desired.

e. Set an embedding such that $G$ lies on an n-dimensional sphere of radius
$r$.

(1) First let $r\leq\frac{\sqrt{2}}{2}$. We proceed inductively. By definition
of $r$, $G$ lies on a unique $\circ_{<}^{[}m]$ of radius $R^{0}(r)=r$. For
$0\leq i$, suppose that $G+K_{i}$ lies on a unique $\circ_{<}^{[}m+i]$, which
has radius $R^{i}(r)$. We must show that $G+K_{i+1}$ lies on a unique
$\circ_{<}^{[}m+i+1]$, which has radius $R^{i+1}(r)$. Well, removing a vertex
yields $G+K_{i}$, which by the inductive hypothesis, lies on a unique
$\circ_{<}^{[}m+i]$ of radius $R^{i}(r)$. By 4.1, re-adjoining the removed
vertex yields a graph that lies on a unique $\circ_{<}^{[}m+i+1]$ of radius
$R(R^{i}(r))=R^{i+1}(r)$. This completes the inductive step and thus the proof
of the first statement.

(2) For $i\leq n$, the proof is identical to the proof of (1). Suppose $i>n$.
Since $G+K_{n}$ does not lie on a $\circ_{<}^{[}]$, the converse of 3.2 yields
that $G+K_{i}$ does lie on a q-dimensional sphere for any $q$. ∎

We now prove 5.6.

_Proof of 5.6._ First suppose that $R_{G}\leq\frac{\sqrt{2}}{2}$, and let $n$
be given. By 5.7c, there exists some $r_{m}>\frac{\sqrt{2}}{2}$ such that
$R^{n}(r_{m})<1$. Since $R_{G}\leq\frac{\sqrt{2}}{2}$, we may choose an
embedding of $G$ such that $G$ lies on a $\circ_{<}^{[}\operatorname{s-dim}G]$
of radius $r<r_{m}$. Fix such an embedding. By 5.7b,
$R^{n}(r)<R^{n}(r_{m})=1$, so by 5.7e(1), $G+K_{n}$ is embedded on a
$\circ_{<}^{[}\operatorname{s-dim}G+n]$. Thus,
$\operatorname{s-dim}(G+K_{n})\leq\operatorname{s-dim}G+n$, completing the
first half of the proof.

Now suppose that $R_{G}>\frac{\sqrt{2}}{2}$. Choose $n$ such that
$R^{n}(R_{G})>1$ (5.7d guarantees such a choice of $n$). If $G+K_{n}$ can be
embedded on a $\circ_{<}^{[}\operatorname{s-dim}G+n]$, it can be constructed
from an embedding of $G$, so set an embedding of $G$. If $G$ lies on a
$\circ_{<}^{[}\operatorname{s-dim}G]$, 5.7e(2) shows that we cannot construct
$G+K_{n}$ on a $\circ_{<}^{[}\operatorname{s-dim}G+n]$. If $G$ lies on a
$\circ_{<}^{[}]$ of greater dimension, iterative application of 4.8 shows that
we cannot construct $G+K_{n}$ on a $\circ_{<}^{[}\operatorname{s-dim}G+n]$.
Finally, if $G$ does not lie on any $\circ_{<}^{[}]$, 3.2 shows that we cannot
extend the embedding of $G$ to an embedding of $G+K_{1}$ and so certainly not
to an embedding of $G+K_{n}$. Regardless, $G+K_{n}$ cannot be embedded on a
$\circ_{<}^{[}\operatorname{s-dim}G+n]$, so
$\operatorname{s-dim}(G+K_{n})>\operatorname{s-dim}G+n$, as desired. ∎

We have now developed the necessary lemmas to compute $\mathbb{S}_{n}$:

######  Theorem 5.8.

For $n>3$, $\mathbb{S}_{n}=\\{K_{n-3}+\epsilon_{3}\\}$.

###### Proof.

Let $S_{n}\in\mathbb{S}_{n}$. Remove all but four vertices from $S_{n}$ to get
$H$. If for every $H$ obtained this way, $K_{3,1}$ is a subgraph of $H$, then
5.5 yields that $K_{n-3}+\epsilon_{3}$ is a subgraph of $S_{n}$. Indeed, since
$S_{n}$ is minor minimal with respect to spherical dimension $n-1$ and
$\operatorname{s-dim}(K_{n-3}+\epsilon_{3})=n-1$ (5.4), $S_{n}$ would equal
$K_{n-3}+\epsilon_{3}$. Thus, it suffices to show that every subgraph of
$S_{n}$ with four vertices obtained by only removing vertices contains
$K_{3,1}$.

Since $\operatorname{s-dim}K_{3}=2$ and $\mathbb{S}_{4}=\\{K_{3,1}\\}$,
$K_{3,1}$ is the only graph with four or fewer vertices that is minor minimal
with respect to spherical dimension 3, so it suffices to show that
$\operatorname{s-dim}H=3$. Suppose to the contrary that
$\operatorname{s-dim}H\neq 3$. Since $\operatorname{s-dim}K_{4}=3$,
$\operatorname{s-dim}H<3$. By 5.3, there are no graphs with four vertices that
have spherical dimension 2 but cannot be embedded on a circle of radius less
than or equal to $\frac{\sqrt{2}}{2}$. Therefore, by 5.6,
$\operatorname{s-dim}(H+K_{n-4})=n-2$. But, by construction of $H$, $S_{n}$ is
a subgraph of $H+K_{n-4}$. Therefore,
$\operatorname{s-dim}S_{n}\leq\operatorname{s-dim}H+K_{n-4}=n-2$. This
contradicts that $\operatorname{s-dim}S_{n}=n-1$. Thus,
$\operatorname{s-dim}H=3$, so $K_{3,1}\subseteq H$, and so
$S_{n}=K_{n-3}+\epsilon_{3}$. ∎

Before moving on, we use our new machinery to improve upon our earlier result,
4.3:

######  Proposition 5.9.

For $n>1$, $K_{n}$ has a unique embedding, which is on an $\circ_{<}^{[}n-1]$
of radius $R^{n-2}\left(\frac{1}{2}\right)$ (which is less than
$\frac{\sqrt{2}}{2}$).

###### Proof.

We proceed by induction. $K_{2}$ has a unique embedding, which is on a
$\circ_{<}^{[}1]$ of radius $R^{0}\left(\frac{1}{2}\right)=\frac{1}{2}$. The
inductive step follows directly from 4.1. ∎

##  6\. Another Class of Graphs Minor Minimal with Respect to Dimension:
$S_{n}+\epsilon_{3}$

The graphs $S_{n}+\epsilon_{3}$ are our second class of minor minimal graphs
with respect to dimension. Before showing this, however, we must first prove a
lemma.

######  Lemma 6.1.

For $n<4$, $S_{n}$ can be embedded on an $\circ_{<}^{[}n-1]$ of any radius
$0<r<1$. For $n\geq 4$, $S_{n}$ can be embedded on an $\circ_{<}^{[}n-1]$ with
any radius $r$ such that $R^{n-4}\left(\frac{1}{2}\right)<r<1$, but cannot be
embedded on any $\circ_{<}^{[}n-1]$ of radius
$r<R^{n-4}\left(\frac{1}{2}\right)$.

###### Proof.

For $n<4$, the proof is trivial. For $n\geq 4$, $S_{n}$ contains a copy of
$K_{n-2}$ as a subgraph (take all $n-3$ vertices of $K_{n-3}$ and any one
vertex of $\epsilon_{3}$), so by 5.9, $S_{n}$ cannot have radius less than
$R^{n-4}\left(\frac{1}{2}\right)$.

To complete the proof, we show that $S_{n}$ can be embedded on an
$\circ_{<}^{[}n-1]$ with any radius between
$R^{n-4}\left(\frac{1}{2}\right)<r<1$. We proceed inductively. Embed $S_{4}$
as follows. Place the three non-center vertices on a $\circ_{<}^{[}2]$, $S$,
place the center vertex as per 4.1, and add the appropriate edges. $S_{4}$ is
now embedded on a sphere $S^{\prime}$. If we send the radius of $S$ to 0, 4.1
shows that the radius of $S^{\prime}$ goes to $\frac{1}{2}$. If we send the
radius of $S$ to 1, the radius of $S^{\prime}$ goes to infinity. Since the
radius of $S^{\prime}$ increases continuously as the radius of $S$ increases,
$S^{\prime}$ can be a $\circ_{<}^{[}3]$ of any radius
$R^{0}\left(\frac{1}{2}\right)=\frac{1}{2}<r<1$.

Now, suppose that $S_{n}$ can be embedded on an $\circ_{<}^{[}n-1]$ of any
radius $R^{n-4}\left(\frac{1}{2}\right)<r<1$ and set any such an embedding.
Since $\operatorname{s-dim}S_{n}=n-1$, $S_{n}$ lies on a unique
$\circ_{<}^{[}n-1]$. Thus, 4.1 allows us to construct $S_{n+1}$ so that it
lies on an $\circ_{<}^{[}n]$ of radius $R(r)$. Letting $r$ run from $R^{n-4}$
to 1 completes the proof by induction. ∎

######  Theorem 6.2.

$S_{n}+\epsilon_{3}$ is minor minimal with respect to dimension $n+1$.

###### Proof.

That $\dim(S_{n}+\epsilon_{3})=n+1$ follows immediately from 3.5 and 5.8. To
show that $S_{n}+\epsilon_{3}$ is minor minimal with respect to dimension, we
must show that every minor of $S_{n}+\epsilon_{3}$, $H$, has dimension less
than $n+1$. We consider three exhaustive cases:

$H$ is obtained by only performing minor operations on $S_{n}$:

In other words, $H=J+\epsilon_{3}$ for some $J\prec S_{n}$. Since $S_{n}$ is
minor minimal with respect to spherical dimension $n-1$,
$\operatorname{s-dim}J<n-1$. Since $\epsilon_{3}$ can be embedded on a
$\circ_{<}^{[}2]$ of any radius, 3.5 yields that $\dim H<n+1$.

$H$ is obtained by contracting at least one edge between $S_{n}$ and
$\epsilon_{3}$ or removing at least one vertex from $\epsilon_{3}$:

Then $H$ is a subgraph of $K_{n}+\epsilon_{2}$. Since
$\operatorname{s-dim}K_{n}=n-1$ and $\epsilon_{2}$ can be embedded on a
$\circ_{<}^{[}1]$ of any radius, $\dim H<n+1$.

$H$ is obtained by removing edges from between $S_{n-3}$ and $\epsilon_{3}$:

It suffices to consider the case when only one edges is removed. Let $v$ and
$u$ be the vertices incident to the removed edge, $v$ from $S_{n}$ and $u$
from $\epsilon_{3}$. Since $S_{n}$ is minor minimal with respect to spherical
dimension, $\operatorname{s-dim}(S_{n}-v)=n-2$. Set an embedding of $S_{n}-v$
on an $\circ_{<}^{[}n-2]$ of radius less than $\frac{\sqrt{2}}{2}$. Add $v$
back to expand this embedding of $S_{n}-v$ into an embedding of $S_{n}$ on an
$\circ_{<}^{[}n-1]$. By 3.3, we may add $\epsilon_{2}$ to the above
construction to get $S_{n}+\epsilon_{2}$ in $\mathbb{R}^{n}$. 3.3 also yields
that the points a distance 1 away from $S_{n}-v$ form a $\circ_{<}^{[}2]$.
Place $u$ anywhere on this $\circ_{<}^{[}2]$ not occupied by $v$ or
$\epsilon_{2}$ and add it to $S_{n}-v$ to complete the embedding of $H$ in
$\mathbb{R}^{n}$. Thus, $\dim H<n+1$.

We have now shown that $\dim H<n+1$ for every $H\prec S_{n}+\epsilon_{3}$, so
we are done. ∎

##  7\. And Another Class of Graphs Minor Minimal with Respect to Dimension:
Flowers

In this section, we add the additional requirement that edges do not cross in
graph embeddings. We will use “embedding” synonymously with “embedding such
that edges do not cross.” The following proposition helps navigate this new
restriction:

######  Proposition 7.1.

Let $G$ and $H$ be graphs. Set an embedding of $G\cupdot H$ in
$\mathbb{R}^{n+m}$ such that $G$ and $H$ lie in planes orthogonal to one
another and every vertex of $G$ is a distance 1 from every vertex of $H$. Then
adding every edge between $G$ and $H$ yields an embedding of $G+H$.

###### Proof.

We must show that the edges between $G$ and $H$ do not cross any other edges.
To do this, construct $G+H$ as in the statement. Without loss of generality,
assume that $G$ lies in the first n coordinates and $H$ lies in the last m
coordinates (i.e., the vertices of $G$ lie on points of the form
$(x_{1},...,x_{n},0,...,0)$ and the vertices of $H$ lie on points of the form
$(0,...,0,x_{n+1},...,x_{n+m})$).

Since the edges within $G$ lie completely inside the surface
$\\{(x_{1},...,x_{n},0,...,0)\\}$ and the edges between $G$ and $H$ lie
completely outside this surface, these edges do not cross. The analogous
statement also holds for the edges within $H$ and edges between $G$ and $H$.

To complete the proof, we must show that two edges between $G$ and $H$ do not
cross. Let $e=(u,v)$ and $e^{\prime}=(u^{\prime},v^{\prime})$ be edges between
$G$ and $H$, with $u,u^{\prime}$ vertices of $G$ and $v,v^{\prime}$ vertices
of $H$. Either $u\neq u^{\prime}$ or $v\neq v^{\prime}$, so without loss of
generality, we may assume $u\neq u^{\prime}$. Indeed, 3.3 shows that $G$ lies
on an n-dimensional sphere centered at the origin, so $u$ and $u^{\prime}$ are
linearly independent. Therefore, the projection of $e$ and $e^{\prime}$ into
the first $n$ dimensions do not cross, and so $e$ and $e^{\prime}$ do not
cross, completing the proof. ∎

Most everything up to this point still holds with the additional restriction
that an embedding is legal only if edges do not cross. Indeed, the proofs are
almost all identical except that we would have to cite the above theorem a few
times.

One notable exception is our work that relied on star n-gons. For example,
$C_{5}$ cannot be embedded on a $\circ_{<}^{[}2]$ of radius less than
$\frac{\sqrt{2}}{2}$ if we do not allow edges to cross. Therefore, using the
argument at the very end of Section 3, we see that
$\operatorname{s-dim}(C_{5}+K_{2})=5>3=\operatorname{s-dim}(C_{5}+K_{1})$.

3.7 is another example. For $n>6$, our embedding of $C_{n}$ on a
$\circ_{<}^{[}2]$ was as a star n-gon, which has crossing edges. Therefore,
$\operatorname{s-dim}C_{n}=3$ for $n\geq 6$ (by using the construction in
Figure 3), and so we get the following analog to 3.7

######  Proposition 7.2.

If edges are not allowed to cross, the dimensions of wheel graphs are

Dimension of $W_{n}^{k}$ | $3\leq n<6$ | $n=6$ | $n>6$
---|---|---|---
$k=1$ | 3 | 2 | 3
$k=2$ | 3 | 4 | 4
$k\geq 3$ | 4 | 5 | 5

Now, notice that $W_{6}^{2}$ is minor minimal with respect to dimension 4 and
$W_{6}^{3}$ is minor minimal with respect to dimension 5. In both cases, the
graph almost fits in one fewer dimension. For example, if we put the two axle
vertices of $W_{6}^{2}$ arbitrarily close together in $\mathbb{R}^{3}$,
$C_{6}$ would have to fit on a circle of radius just less than 1, but $C_{6}$
can only fit on a circle of radius 1. Similarly, if we put the three axle
vertices of $W_{6}^{3}$ on a circle of arbitrarily small radius in
$\mathbb{R}^{4}$, $C_{6}$ would again have to fit on a circle of radius just
less than 1. In both cases, adding the extra dimension allows us to embed
$C_{6}$ on a $\circ_{<}^{[}3]$ (using the construction in Figure 3) and thus
the wheel graph.

Figure 8. A few graphs in $\mathcal{F}_{4}^{2}$. They can be obtained by
splitting zero, one, or all the spokes of $W_{4}^{2}$, respectively.

Flower graphs are a generalization of wheel graphs. If we split an arbitrarily
number of “spokes” of the $W_{6}^{2}$, we get what we call the 6-Flowers with
$\epsilon_{2}$ center, denoted $\mathcal{F}_{6}^{\epsilon_{2}}$. More
precisely, we define petals by

$\mathcal{P}_{n}=\left\\{P\;|\;\begin{aligned} &\text{$P$ has $n$ edges, and
each vertex of $P$}\\\ &\text{ is incident to either one or two
edges}\end{aligned}\right\\}$

and flowers by

$\mathcal{F}_{n}^{G}=\\{G+P\;|\;P\in\mathcal{P}_{n}\\}.$

The following is the main theorem of this section:

######  Theorem 7.3.

The following flower graphs are minor minimal:

  * •

$\mathcal{F}_{6}^{S_{1}}-\\{W_{6}\\}$ with respect to dimension 3,

  * •

$\mathcal{F}_{6}^{S_{n}}$ ($1<n<5$) with respect to dimension $n+2$,

  * •

$\mathcal{F}_{5}^{S_{n}}$ ($n\geq 5$) with respect to dimension $n+2$.

Before we prove this theorem, we need to state and prove some lemmas.

######  Lemma 7.4.

Let $r_{n}$ be the circum-radius of the regular convex n-gon.

a:

For all $n$, $S_{n}$ can be embedded on an $\circ_{<}^{[}n-1]$ of radius less
than $\sqrt{1-r_{4}^{2}}$.

b:

For $1\leq n\leq 4$, $S_{n}$ can be embedded on a $\circ_{<}^{[}3]$ of radius
less than $\sqrt{1-r_{5}^{2}}$.

c:

For $n>4$, $S_{n}$ cannot be embedded on an $\circ_{<}^{[}n-1]$ of radius less
than or equal to $\sqrt{1-r_{5}^{2}}$.

###### Proof.

To prove the three claims, we simply need to do some computations. 6.1 will do
most of the work for us.

a. Direct computation yields $r_{4}=\frac{\sqrt{2}}{2}$, and 6.1 and 4.2a
yield that $S_{n}$ can be embedded on an $\circ_{<}^{[}n-1]$ of radius less
than $\frac{\sqrt{2}}{2}=\sqrt{1-r_{4}^{2}}$.

b. Direct computation yields $1-r_{5}^{2}=\frac{5+\sqrt{5}}{10}$, and 6.1
yields that $S_{n}$ can be embedded on a $\circ_{<}^{[}3]$ of radius
arbitrarily close to $\frac{1}{2}<\sqrt{1-r_{5}^{2}}$.

c. By 6.1, $S_{5}$ cannot be embedded on a $\circ_{<}^{[}4]$ of radius less
than $R\left(\frac{1}{2}\right)>\sqrt{1-r_{5}^{2}}$. Thus, 5.7a shows that
$S_{n}$ cannot be embedded on an $\circ_{<}^{[}n-1]$ of radius less than
$\sqrt{1-r_{5}^{2}}$ for all $n>4$. ∎

######  Lemma 7.5.

Every proper minor of $S_{n}$ can be embedded on an $\circ_{<}^{[}n-2]$ of
radius $\frac{\sqrt{2}}{2}$.

###### Proof.

The proper minors of $S_{n}$ are all subgraphs of $K_{n-4}+(P_{3}\cupdot
vertex)$ or $K_{n-5}+K_{3,2}$. Therefore, it suffices to show that both of
these graphs can be embedded on an $\circ_{<}^{[}n-2]$ of radius
$\frac{\sqrt{2}}{2}$.

In both cases, we will write the graph as the sum of two graphs, $G+H$, and
show that $G$ can be embedded on an $\circ_{<}^{[}m]$ and $H$ on an
$\circ_{<}^{[}m^{\prime}]$ such that $m+m^{\prime}=n-2$. This is sufficient
because we can then embed $G$ on an $\circ_{<}^{[}m]$ and $H$ on an
$\circ_{<}^{[}m^{\prime}]$ that have the same center but lie in orthogonal
planes. Adding all edges between $G$ and $H$ will then yield an embedding of
$G+H$ on an $\circ_{<}^{[}n-2]$ of radius $\frac{\sqrt{2}}{2}$.

Since $K_{n-4}$ can be embedded on an $\circ_{<}^{[}n-5]$ of radius less than
$\frac{\sqrt{2}}{2}$ (4.3), it can be embedded on an $\circ_{<}^{[}n-4]$ of
radius $\frac{\sqrt{2}}{2}$. It is easy too see that $P_{3}\cupdot vertex$ can
be embedded on a $\circ_{<}^{[}2]$ of radius $\frac{\sqrt{2}}{2}$.

Since $K_{n-5}$ can be embedded on an $\circ_{<}^{[}n-6]$ of radius less than
$\frac{\sqrt{2}}{2}$, it can be embedded on an $\circ_{<}^{[}n-5]$ of radius
$\frac{\sqrt{2}}{2}$. Additionally, $K_{3,2}$ can be embedded on a
$\circ_{<}^{[}3]$ of radius equal to $\frac{\sqrt{2}}{2}$. ∎

######  Lemma 7.6.

For $3\leq n\leq 6$, $P\in\mathcal{P}_{n}$ can be embedded on circle (but
obviously not two points). Moreover, $P$ can be embedded on all circles of
radius greater than $r_{n}$ but cannot be embedded on any circle of radius
less than $r_{n}$.

###### Proof.

This is straight-forward after recalling the definitions of $R_{P}$ and
$r_{n}$ (which appear directly before 5.3 and in 7.4, respectively). ∎

######  Lemma 7.7.

For $4\leq n\leq 6$, suppose some minor operation is performed on
$P\in\mathcal{P}_{n}$ to get $P^{\prime}$. Then $R_{P^{\prime}}\leq r_{n-1}$.

###### Proof.

The main idea is to use that $R_{P^{\prime}}\leq r_{n-1}$ if
$P^{\prime}\in\mathcal{P}_{n-1}$. We break the proof into two exhaustive
cases:

$P^{\prime}$ does not have a disjoint vertex:

Then $P^{\prime}\in\mathcal{P}_{n-1}$, and so we are done.

$P^{\prime}$ has a disjoint vertex:

Let $v$ be the disjoint vertex. Then $P^{\prime}-v\in\mathcal{P}_{n-1}$, and
so we can complete the embedding of $P^{\prime}$ by placing $v$ on any
unoccupied spot on the circle.

∎

If $P\in\mathcal{P}_{n}-\\{C_{n}\\}$, we can strengthen the above lemma:

######  Lemma 7.8.

Let $4\leq n\leq 6$. If $P^{\prime}$ is a minor of
$P\in\mathcal{P}_{n}-\\{C_{n}\\}$, then $P^{\prime}$ can be embedded on a
circle, $S$, of radius arbitrarily close to $r_{n-1}$ such that a straight
line can be drawn from the center of $S$ to any vertex of $P^{\prime}$ without
crossing an edge.

###### Proof.

The proof is almost identical to that of 7.7. We need only slightly revise the
second case:

$P^{\prime}$ has a disjoint vertex:

Proceed as before, but place $v$ on any unoccupied spot on $S$ such that a
straight line can be drawn from the center of $S$ to $v$ without crossing an
edge of $P^{\prime}$.

∎

We now prove 7.3:

_Proof of 7.3._
a. Recall that $\dim W_{6}=2$, so $W_{6}$ is not minor minimal with respect to
dimension 3. Let $F_{6}\in\mathcal{F}_{6}^{S_{1}}-\\{W_{6}\\}$, and let $P$ be
$F_{6}$’s petals. $F_{6}$ can be embedded in $\mathbb{R}^{m}$ if and only if
$P$ can be embedded on an unit m-dimensional sphere. Since $P$ cannot be
embedded on a unit circle, $\dim F_{6}\geq 3$. However, $P$ can be embedded on
a unit sphere (as demonstrated in Figure 3), so $\dim F_{6}=3$.

We must now show that $\dim H<3$ for every $H\prec F_{6}$. We consider a few
exhaustive cases:

$S_{1}$ is deleted:

Then $H$ is a subgraph of $P$. Since $\dim P_{6}=1$, $\dim H\leq 1<3$.

A minor operation is performed on $P$, or an edge between $S_{1}$ and $P_{6}$
is contracted:

In either case, the resulting graph is a subgraph of $S_{1}+P^{\prime}$, where
$P^{\prime}\prec P$. The result now follows from 7.8.

An edge between $P$ and $S_{1}$ is deleted:

Figure 9 suggests the proof.

Figure 9. $F_{6}$ cannot be embedded in $\mathbb{R}^{2}$, as can be seen in
the left-most graph. However, if we remove an edge between a petal vertex and
the central vertex, we get a graph akin to one of the two right-most graphs,
which can be embedded $\mathbb{R}^{2}$.

Therefore, regardless, $\dim H<3$, as desired.

b. Let $F_{6}\in\mathcal{F}_{6}^{S_{n}}$ for some $1<n<5$, and let $P$ be its
petals. Notice that $P$ has spherical dimension 3 and can be embedded on a
$\circ_{<}^{[}3]$ of any radius greater than $\frac{1}{2}$. This, in tandem
with 7.4a and 3.5, shows that $\dim F_{6}=n+2$.

Now, let $H\prec F_{6}$. We must show that $\dim H<n+2$. We consider a few
exhaustive cases:

Minor operations are performed on $S_{n}$, but no edges are contracted between
$S_{n}$ and $P$:

From 7.5, every minor of $S_{n}$ can be embedded on an $\circ_{<}^{[}n-2]$ of
radius $\frac{\sqrt{2}}{2}$. Since $P$ can be embedded on a $\circ_{<}^{[}3]$
of radius $\frac{\sqrt{2}}{2}$, 3.5 yields that $\dim H=n+1<n+2$.

A minor operation is performed on $P$, or an edge between $S_{n}$ and $P$ is
contracted:

In either case, the resulting graph is a subgraph of $K_{n}+P^{\prime}$, where
$P^{\prime}\prec P$. Using 5.9, we see that $K_{n}$ can be embedded on an
$\circ_{<}^{[}n-1]$ of radius less than $\sqrt{1-r_{5}^{2}}$, and by 7.7,
$P^{\prime}$ can be embedded on a $\circ_{<}^{[}2]$ of any radius greater than
$r_{5}$. Thus, 3.5 yields that $\dim H=n+1<n+2$.

An edge between $S_{n}$ and $P$ is deleted:

7.4b together with Figure 9 suggests the proof.

c. Let $F_{5}\in\mathcal{F}_{5}^{S_{n}}$ for some $n\geq 5$, and let $P$ be
its petals. Notice that $P$ can be embedded on a $\circ_{<}^{[}3]$ of any
radius greater than $\frac{1}{2}$. This in tandem with 7.4a shows that $F_{5}$
can be embedded in $\mathbb{R}^{n+2}$. Moreover, 7.6, 7.4c, and 3.5 shows that
$\dim F_{5}>n+1$. Therefore, $\dim F_{5}=n+1$¿

Now, let $H\prec F_{5}$. We must show that $\dim H<n+2$. We consider a few
exhaustive cases.

Minor operations are performed on $S_{n}$, but no edges are contracted between
$S_{n}$ and $P$:

From 7.5, every minor of $S_{n}$ can be embedded on an $\circ_{<}^{[}n-2]$ of
radius $\frac{\sqrt{2}}{2}$. Since $P$ can be embedded on a $\circ_{<}^{[}3]$
of radius $\frac{\sqrt{2}}{2}$, 3.5 yields that $\dim H=n+1<n+2$.

A minor operation is performed on $P$, or an edge between $S_{n}$ and $P$ is
contracted:

In either case, the resulting graph is a subgraph of $K_{n}+P^{\prime}$, where
$P^{\prime}\prec P$. By 4.3, $K_{n}$ can be embedded on an $\circ_{<}^{[}n-1]$
of radius less than $\frac{\sqrt{2}}{2}$, and by 7.7, $P^{\prime}$ can be
embedded on a $\circ_{<}^{[}2]$ of any radius greater than
$\frac{\sqrt{2}}{2}$. Thus, 3.5 yields that $\dim H=n+1<n+2$.

An edge between $S_{n}$ and $P$ is deleted:

7.4a together with Figure 9 suggests the proof.

∎

Notice that 7.3 does not hold with our previous notion of dimension. This is
because we could then stack petals on top of one another as in the left-most
graph in Figure 9. Therefore, most of the flower graphs we have considered
would have dimension $n+1$ rather than $n+2$. However, this stacking method
does not work if the petals are a cycle graph. Therefore, $S_{n}+C_{6}$ still
has dimension $n+2$ for $1<n<5$ and so is still minor minimal. Similarly
$S_{n}+C_{5}$ is still minor minimal for $n\geq 5$. This is our final result:

######  Corollary 7.9.

Using the definition of dimension used in the previous sections, the following
flower graphs are minor minimal with respect to dimension $n+2$:

  * •

$S_{n}+C_{6}$ for $1<n<5$,

  * •

$S_{n}+C_{5}$ for $n\geq 5$.

##  8\. Acknowledgments

The first author would like to thank co-advisor Dr. Harold Ellingsen for his
patient and prudent mentorship. He would also like to thank all of his
colleagues from the Potsdam REU, especially Ioherase Ransom and Jessica Mean.
Their engagement in speculative conversations helped make this paper possible.

This research was conducted through the SUNY Potsdam/Clarkson University REU,
with funding from the National Science Foundation under Grant No. DMA-1262737
and the National Security Administration under Grant No. H98230-14-1-0141.

## References

  * [1] Colin de Verdière, Y. “Sur un nouvel invariant des graphes et un critère de planarité.” _Journal of Combinatorial Theory, Series B_ , 1 (1990), 11–21.
  * [2] Erdős, P., Harary, F., and Tutte, W.T. “On the Dimension of a Graph.” _Mathematika_ , 12 (1965), 118-122.
  * [3] van der Holst, H, Lovász, L, Schrijver, A. “The Colin de Verdière Graph Parameter.” _Graph Theory and Combinatorial Biology_ , 7 (1999), 29-85.
  * [4] Kotlov, A, Lovász, L, Vempala, S. “The Colin de Verdiere Number and Sphere Representations of a Graph.” _Combinatorica_ , 17 (1997), 483-521.
  * [5] Kuratowski, K. “Sur le problème des courbes gauches en topologie.” _Fund. Math._ , 15 (1930), 271-283.
  * [6] Lovász, L, Schrijver, A. “A Borsuk Theorem for Antipodal Links and a Spectral Characterization of Linklessly Embeddable Graphs.” _Proceedings of the American Mathematical Society_ 126 (1998), 1275-1285.
  * [7] Weisstein, Eric W. “Star Polygon.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/StarPolygon.html