Saturation of $K_4$ subdivisions in multidimensional grids

1. Introduction

1.1. Background

Suppose $\mathcal{F}$ is a family of graphs. We say that a graph $G$ is $\mathcal{F}$–saturated if no element of $\mathcal{F}$ is a subgraph of $G$, but for any edge $e$ in the complement of $G$, $G+e$ contains a subgraph isomorphic to some $F\in \mathcal{F}$. When $\mathcal{F}=\{L\}$ is a single graph $L$, and G satisfies the preceding conditions, then we say that $G$ is $L$-saturated. The well studied Turan function $ex(n,\mathcal{F})$ is the maximum number of edges in any $\mathcal{F}$-saturated graph on $n$ vertices. A natural dual to $ex(n,\mathcal{F})$ is the saturation function $Sat(n,\mathcal{F})$, which is the minimum number of edges in any $\mathcal{F}$-saturated graph on $n$ vertices. We write $Sat(n,L)$ and $ex(n,L)$ for these two functions when $\mathcal{F}=\{L\}$; that is, when $\mathcal{F}$ consists of the single graph $L$. The best known upper bound on $Sat(n,\mathcal{F})$ for an arbitrary family $\mathcal{F}$ is given in [27].

A natural first case to study for the saturation function is $Sat(n,K_r)$, where $K_r$ is the complete graph on $r$ vertices. It was shown in [39] and later independently in [15] that $Sat(n,K_r)=(r-2)(n-r+2)+(\genfrac{}{}{0ex}{}{r-2}{2})=(\genfrac{}{}{0ex}{}{n}{2})–(\genfrac{}{}{0ex}{}{n-r+2}{2})$, and that the upper bound is uniquely realized by the join $K_{r-2}+{\overline{K}}_{n-r+2}$; that is, the disjoint union of $K_{r-2}$ with a set of $n-r+2$ independent points, together with all $(r-2)(n-r+2)$ possible edges joining the set of independent points with the vertices of the $K_{r-2}$. At the opposite extreme in edge density from $K_r$ for connected graphs is the star $K_{1,t}$, where there is the following result.

Let $H$ be a fixed graph (and we think of $H$ as the “host”), and $L$ a given graph (where we think of $L$ as the “forbidden” graph). A subgraph $G$ of $H$ is called $L$–saturated in $H$ (or just $L$–saturated if $H$ is understood) if $L$ is not a subgraph of $G$, but for any edge $e\in E(H)–E(G)$ the graph $G+e$ contains the subgraph $L$. We then let $ex(H,L)$ and $Sat(H,L)$ be the maximum and minimum (respectively) number of edges in a graph $G$ which is $L$-saturated in $H$. If $L$ is not a subgraph of $H$ then we let $Sat(H,L)=ex(H,L)=|E(H)|$. Observe also that $Sat(n,L)=Sat(K_n,L)$ and $ex(n,L)=ex(K_n,L)$.

This saturation problem for general host graphs $H$ was to our knowledge first mentioned in [15]. Erdos examined $Sat(H,K_3)$ in [13]. In [15] the value of $Sat(K_{r,s},K_{m,n})$, $m\le r$ and $n\le s$, was conjectured, where we specify that the $m$-set (resp. $n$-set) of the $K_{m,n}$ occur in the $r$-set (resp. $s$-set) of the $K_{r,s}$. The conjecture was confirmed independently by Bollobás [6], [3], and Wessel [], [37], where they showed that $Sat(K_{r,s},K_{m,n})=rs–(r–m+1)(s–n+1)$. Let $Sa{t}^{\prime }(K_{r,s},K_{m,n})$ be the saturation function for the unordered version of this problem; that is, where we allow the $m$-set of $K_{m,n}$ to be either in the $r$-set or the $s$-set of $K_{r,s}$, and the $n$-set is in the opposite set of $K_{r,s}$. In [33] it was conjectured that $Sa{t}^{\prime }(K_{r,r},K_{m,n})=(m+n–2)r–\lfloor (\frac{m+n-2}{2}{)}^2\rfloor$. In [20] it was shown that $Sa{t}^{\prime }(K_{r,r},K_{m,n})\ge (m+n–2)r–(m+n–s{)}^2$ and that the conjecture holds in the case $m=2$ and $n=3$.

Another host graph that has been considered is the complete multipartite graph. The above saturation results for bipartite hosts were generalized to $k$-uniform multipartite hypergraph hosts by Alon [2]. In this paper he proves a result on extremal sets using methods of multilinear algebra, and from this derives results on saturation in multipartite hypergraphs. The bipartite host results were also generalized by Pikhurko in his Ph.D. thesis at Cambridge [34]. Now let $K_k^n$ be the complete multipartite graph on $k$ partite sets, each of size $n$. In [18] the values of $Sat(K_k^n,K_3)$ were determined for all $k\ge 4$ for large enough $n$, and also determined for $Sat(K_3^n,K_3)$ for all $n$.

For any graph $G$, let $S(G)$ denote the set of all graphs that can be obtained from $G$ by inserting any number of points of degree 2 along any set of edges of $G$, and we call any such graph a subdivision of $G$. Some also call this set of graphs $T(G)$, and any member of $T(G)$ a topological $G$. Slightly abusing notation and for brevity, we sometimes refer to an arbitrary member of $S(G)$ as an $S(G)$ or just by the symbol $S(G)$.

There has been substantial research concerning subdivisions of graphs in the context of both the saturation function $Sat(n,L)$ and the Turan function $ex(n,L)$. A direct influence on our work here was the paper [17], which we discuss below. In [29] the set of possible values $|E(H)|$ for $C_k$-saturated saturated graphs $H$ (where $C_k$ is the cycle on $k$ points) was determined. Next we mention results related to the Turan number for subdivision families. In [5] the authors investigate $ex(n,S(F))$, where $F$ is obtained from a cycle by joining a point on the cycle with edges only to points off the cycle, or only to points on the cycle, and again $S(F)$ is the family of all subdivisions of such an $F$. We mention also the deep papers [24], [23], and [12], among others, exploring $ex(n,S(F))$ where $F$ is the complete bipartite graph in some cases. One of the goals in this research is to find, for a given graph $G$ the exponent $r,1<r<2,$ for which $ex(n,G)=\mathrm{\Theta }(n^r)$. Another goal is to show that for any such $r$ there is a graph $G$ for which $ex(n,G)=\mathrm{\Theta }(n^r)$.

Moving closer to “gridlike” graphs, we mention work on saturation in the hypercube, denoting by $Q_n$ the hypercube of dimension $n$. In [11] it was shown that $Sat(Q_n,Q_2)\le (\frac{1}{4}+o(1))|E(Q_n)|$, and conjectured that this bound was best possible. In [25] this conjecture was disproved, where it was shown that for every fixed $m$, there exists a $Q_m$-saturated subgraph of $Q_n$ with $o(|E(Q_n))$ edges. They also improved on the earlier bound on $Sat(Q_n,Q_2)$ by showing that $Sat(Q_n,Q_2)<10\cdot 2^n$ and asked for which $m$ is it true that $Sat(Q_n,Q_m)=O(2^n)$. It was shown in [32] that this holds for every $m\ge 2$, specifically, that $Sat(Q_n,Q_m)\le (1+o(1))72m^2{2}^n$.

In a related paper [31] to this one, the authors considered as a host the multidimensional grid $P_m^r=P_m\times P_m\times \cdots \times P_m$; that is, the $r$-fold cartesian product of paths $P_m$ on $m$ points as the host graph, where the guest graph is the star $K_{1,t}$. In that paper the following results for the function $Sat(P_m^r,K_{1,t})$ were proved.

In this paper we continue the study of saturation in the host $P_m^r$. Let $S(K_4)$ be the family of all graphs which are subdivisions of $K_4$. In this paper we obtain results on $Sat(P_m^r,S(K_4))$. Definitions and the precise statement of results follow in the next subsection.

It is useful to mention the connection of the saturation function $Sat(G,H)$ to applications in the area of bootstrap percolation, where we have drawn on [8] and [30] for the overview which follows. In that area the general idea is to analyze diffusion or infection processes which spread through the vertices or edges of a graph. As such, this models in this area are useful in describing magnetic materials, fluid flow in rocks, computer storage systems, and spreading of rumors. So this area has been of interest to physicists, computer scientists, and sociologists; see [1] and [35].

In the vertex version, we begin with a starter set of vertices $A_0\subseteq V(G)$ in some graph $G$, and then build a sequence of sets $A_t\subseteq V(G)$, $t\ge 0$, where $A_t\supseteq A_{t-1}$ for $t\ge 1$, according to some rule. Letting $⟨A_0⟩={\cup }_{t\ge 0}{A}_t$, one question of interest is whether $⟨A_0⟩=V(G)$; that is, whether the process diffuses to all vertices in $G$. In this case we say that $A_0$ percolates $G$, or that $A_0$ is a percolating set for $G$.

A popular model of bootstrap percolation is $r$–neighbor bootstrap percolation, where the diffusion process is given by $A_{t+1}=A_t\cup \{v\in V(G):|N(v)\cap A_t|\ge r\}$. Thus a vertex joins set $A_{t+1}$ if at least $r$ of its neighbors are already in $A_t$; that is these neighbors have already been infected by time $t$. One may choose $A_0$ randomly (see [9]); that is, each vertex is initially infected with probability $p$ independently of all other vertices. We then consider the event $⟨A_0⟩=V(G)$, and define the critical percolation probability by

$$p_c(G,r)=inf\{p:Pro{b}_p[⟨A_0⟩=V(G)]\ge \frac{1}{2}\},$$

The class of $d$-dimensional grids $P_m^d$ is of interest as a possible graph $G$ for this work. Among the results here we mention the work of Holroyd [22] who proved $p_c(P_m^2,2)={\displaystyle \frac{{\pi }^2}{18log(n)}}+o\left({\displaystyle \frac{1}{log(n)}}\right)$. Holroyd introduced a function $\lambda (d,r)$ (which we omit here), which was used by Balogh [4] in proving the sharp threshold for all dimensions $d$ given by

$$p_c(P_m^d,r)=({\displaystyle \frac{\lambda (d,r)+o(1)}{lo{g}_{r-1}(n)}}{)}^{d-r+1},$$ where $lo{g}_{r-1}(n)$ is the $(r-1)$-times iterated logarithm.

Another model considers a diffusion process through edges called $H$–bootstrap percolation. As notation, for any set $S$ of edges in some graph $G$, let $[S]$ denote the subgraph of of $G$ induced by $S$. Now let $G$ and $H$ be graphs, and $E_0\subseteq E(G)$ such that $H$ is not a subgraph of $[E_0]$. We say that $E_0$ is weakly $H$-saturated in $G$ if there is an ordering $e_1,e_2,\cdots ,e_k$ of the edges in $E(G)–E_0$ such that for the edge sets $E_1=E_0\cup \{e_1\}$, and generally $E_i=E_{i-1}\cup \{e_i\}$, $1\le i\le k$, the following holds. For each $i\ge 1$ there is a subgraph $H^{\prime }\cong H$ contained in $E_i$, but $H^{\prime }$ not contained in $E_{i-1}$. That is, the addition of edge $e_i$ creates a copy of $H$ in $E_i$ not present in $E_{i-1}$. The research problem, proposed by Bollobás in [7], is then to find a minimum size weakly $H$-saturated set in $G$, denoted by $wsat(G,H)$.

In an equivalent model for $H$-bootstrap percolation, starting again with some $E_0\subseteq E(G)$, we build a sequence $E_0\subset E_1\subset E_2\cdots$ of edge sets $E_i\subseteq E(G)$ of $G$ according to the following rule:

$$E_{t+1}=\{e\in E(G)-E_t:\mathrm{\exists }{H}^{\prime }\cong H\text{with}{H}^{\prime }\subseteq [E_t\cup \{e\}]\text{and}{H}^{\prime }⊈[E_t]\}.$$

If $E_k=E(G)$ for some $k\ge 0$, then we say that our “starter” set $E_0$ is an $H$-percolating set in $G$. Here we add entire sets of edges to our percolating process at a time. Note that for any $E^{\prime }\subseteq E(G)$ we have that $E^{\prime }$ is weakly $H$-saturated in $G$ if and only if $E^{\prime }$ is $H$-percolating in $G$. Clearly the minimum size of an $H$-percolating set in $G$ is also $wsat(G,H)$. In this second model one can also ask for the maximum time $t$, over all starting sets $E_0$, until the percolation process stabilizes; that is until $E_{t+1}=E_t$. We mention [8] and [30] among others for work on this topic.

For the connection between the saturation function $Sat(G,H)$ studied in this paper and percolation, observe that $wsat(G,H)\le Sat(G,H)$. As proof, take any edge set $E^{\prime }\subseteq E(G)$ realizing $Sat(G,H)$. Then $E^{\prime }$ is in fact weakly saturated in $G$. This is because by definition $H⊈[E^{\prime }]$, and for any $e\in E(G)–E^{\prime }$ we have $H\subseteq E^{\prime }\cup \{e\}$. Thus under any ordering $e_i,i\ge 1$, of the edges in $E(G)–E^{\prime }$ the sets $E_i$ given by $E_0=E^{\prime }$, and $E_i=E_{i-1}\cup \{e_i\}$ for $i\ge 1$ gives a process witnessing that $E^{\prime }$ is weakly $H$-saturated in $G$; that is a process for which $E_k=E(G)$, where $k=|E(G)|–|E^{\prime }|$. Thus $wsat(G,H)\le |E^{\prime }|=Sat(G,H)$. Bollobás conjectured that we have equality for the $K_r$-percolation process in $K_n$; that is $wsat(K_n,K_r)=Sat(K_n,K_r)=(\genfrac{}{}{0ex}{}{n}{2})–(\genfrac{}{}{0ex}{}{n-r+2}{2})$, the last equality having already been mentioned in our introduction. This conjecture was verified independently in [2], [26], and [19].

Thus the upper bounds and exact results on $Sat(P_m^r,S(K_4))$ provided in this paper also act as upper bounds for $wsat(P_m^r,S(K_4))$; that is, for the minimum size of starter set in the $S(K_4)$-bootstrap percolation on $P_m^r$. More generally one can use upper bounds on $Sat(G,H)$ to give upper bounds on the minimum size of a starter $E_0$ which percolates $G$ in the $H$-percolation process on $G$.

Finally we mention the dynamic survey [16] which gives a broad and detailed coverage of the area of saturation in graphs and hypergraphs. Another useful survey is given by Gould in [21], among other works on saturation by this author.

1.2. Definitions and saturation in grids

We begin with some definitions, starting with the multidimensional grid $P_m^r$ for positive integers $r\ge 2$ and $m\ge 3$. It has vertex set $V(P_m^r)=\{x=(x_1,x_2,\cdots ,x_r):x_i$ an integer with $1\le x_i\le m\}$, so vertices are $r$-tuples $x$ with $i$’th coordinate $x_i$ being an integer in $[m]$. The edge set is given by $E(P_m^r)=\{xy:x,y\in V(P_m^r),\sum _{i=1}^r|x_i–y_i|=1\}.$ So $xy$ is an edge in $P_m^r$ precisely when $x$ and $y$ disagree in exactly one coordinate, and in that coordinate they differ by $1$. A straightforward induction shows that $|E(P_m^r)|=r{m}^r–r{m}^{r-1}$.

For any subgraph $T$ of $P_m^r$, we let $T(i)$ be the subgraph of $T$ induced by points of $T$ with $r$’th coordinate equal to $i$, $1\le i\le m$. For an edge $xy\in E(P_m^r)$, we say that $xy$ is a $k$-dimensional edge if $x$ and $y$ disagree by $1$ in their $k$’th coordinates, and hence that $x_i=y_i$ for $i\ne k$. For a graph $H$ and subgraph $G\subset H$, we say that an edge $e\in E(H)–E(G)$ is a nonedge of $G$ in $H$, and we let $H[\overline{G}]$ be the subgraph of $H$ induced by the set of nonedges of $G$ in $H$.

Next, given graphs $G$ and $H$ we let $G\times H$, called the cartesian product of $G$ and $H$, be defined by $V(G\times H)=\{(v,w):v\in V(G),w\in V(H)\}$ and $E(G\times H)=\{(v_1,w_1)(v_2,w_2):v_1=v_2$ and $w_1{w}_2\in E(H)$, or $w_1=w_2$ and $v_1{v}_2\in E(G)\}.$ Note that $G\times H$ can be obtained from $G$ by replacing each vertex $v$ of $G$ by its own copy, call it $H_v$, of $H$, and joining two such copies $H_v$ and $H_{v^{\prime }}$ by a matching joining corresponding points in these two copies precisely when $v{v}^{\prime }\in E(G)$. Symmetrically, $G\times H$ can also be obtained by doing the similar replacement of vertices of $H$ by copies of $G$. Thus $P_m^r$ is just the $r$-fold cartesian product $P_m\times P_m\times \cdots \times P_m$. In our illustrations of $P_m\times P_n$ and its subgraphs, rows are drawn from top to bottom in increasing row number. Also columns are drawn left to right in increasing column number. So point $(a,b)\in P_m\times P_n$ is in the $a$’th row from the top and the $b$’th column from the left.

We now turn to subdivisions of complete graphs as the forbidden graph for the saturation function. Clearly any member of $S(K_3)$ is a cycle, so $Sat(n,S(K_3))=n-1$ as realized by a spanning tree of $K_n$. Next, it is straightforward to show that any $K_4$ minor is a member of $S(K_4)$ (see also Proposition 1.7.2 in [13] for a more general observation). It is also shown in [13] (Proposition 8.3.1) that any edge maximal graph without a $K_4$ minor must be a $2$-tree, so it follows that $ex(n,S(K_4))=Sat(n,S(K_4))=2n-3$.

An exact result for $Sat(n,S(K_5))$ and upper bounds for $Sat(n,S(K_t)),t\ge 6$ were given in the following result. This result motivated our work on $Sat(P_m^r,S(K_4))$ which follows that result:

The main results of this paper are the following.

1. If at least one of $m$ or $n$ is odd with $m\ge 5$ and $n\ge 5$, then $Sat(P_m\times P_n,S(K_4))=mn+1.$

2. For $m$ even and $m\ge 4$, we have $m^3+1\le Sat(P_m^3,S(K_4))\le m^3+2.$

3. For $r\ge 3$ with $m$ even and $m\ge 4$, we have $Sat(P_m^r,S(K_4))\le m^r+2^{r-1}–2$.

We use standard graph theoretic notation, as may be found for example in the texts [38] or [10]. There will be additional notation introduced when needed throughout the paper.

2. $S(K_4)$-saturation in dimension 2

The following Lemma gives the lower bound for our exact result in dimension $2$:

We will need the following obvious remark for future reference:

3. $S(K_4)$-saturation in dimension 3

In this section we give a construction that realizes upper bounds for $Sat(P_m^3,S(K_4))$, $m$ even and $m\ge 4$. It provides the basic intuition behind our general construction realizing upper bounds for $Sat(P_m^r,S(K_4))$ for arbitrary dimension $r\ge 4$ that we give in the next section. We refer to the four points of degree $3$ in an $S(K_4)$ as junction points of that $S(K_4)$, and to the six internally disjoint paths in this $S(K_4)$ joining pairs of junction points as junction paths.

For any subset $S\subset V(P_m^u)$, $u\ge 1$, we let $\underset{\_}{S\ast i}\subset V(P_m^{u+1})$ be defined by $S\ast i=\{(x_1,x_2,\cdots ,x_u,i):(x_1,x_2,\cdots ,x_u)\in S\}$; that is $S\ast i$ is obtained by appending $i$ as the $(u+1)$’st coordinate and leaving the first $u$ coordinates unchanged in each point of $S$. For example if $S=\{(1,2,1),(2,3,4)\}\subset V(P_m^3)$, then $S\ast 3=\{(1,2,1,3),(2,3,4,3\}\subset V(P_m^4)$. Similarly if $T$ is a subgraph of $P_m^u$, then $T\ast i$ is the subgraph of $P_m^{u+1}$ induced by the vertex set $V(T)\ast i$. So clearly $T\ast i\cong T$ under the natural isomorphism $(x_1,x_2,\cdots ,x_u)\mapsto (x_1,x_2,\cdots ,x_u,i)$ over all $(x_1,x_2,\cdots ,x_u)\in V(T)$.

We begin by constructing a subgraph $S_2\subset P_m^2$ for $m$ even:

3.1. Construction of subgraph $S_2\subset P_m^2$, $m$ even

1. Let $V(S_2)=V(P_m^2)$

2. Let $S{Q}_2$ be the subgraph of $P_m^2$ induced by the boundary cycle of $P_m^2$; that is, $S{Q}_2$ is the graph induced by the set of edges $\{(x,j)(x,j+1):x=1$ or $m,1\le j\le m-1\}\cup \{(i,y)(i+1,y):y=1$ or $y=m,1\le i\le m-1\}$.

3. For every vertex $v=(s,1)\in S_2(1)$ and $w=(s,m)\in S_2(m)$, $2\le s<m$, define the path $D(v,2)$ by;

   1. if $s$ is even, then $D(v,2)=(s,1)–(s,2)–(s,3)–\cdots –(s,m-1)$, and

   2. if $s$ is odd, then $D(v,2)=(s,2)–(s,3)–(s,4)–\cdots –(s,m)$.

   3. For $w=(s,m)$, let $D(w,2)=D((s,1),2)$.

   4. Let $D(2)={\cup }_{v=(s,1),2\le s<m}D(v,2)$

4. Let $S_2=S{Q}_2\cup D(2)$.

End of construction of $S_2$.

Each of the two rectangles in Figure 2 consisting of straight horizontal or vertical edges is a copy of $S_2$. The curved lines are used in the construction of $S_3\subset P_m^3$ which follows, and can be ignored for now. Apart from the boundary of $S_2$, the horizontal straight lines represent paths $D(v,2)$. For example, (suppressing third coordinates) we have $D((2,1),2)=(2,1)-(2,2)\cdots –(2,m-1)$ and $D((m-1,1),2)=(m-1,2)-(m-1,,3)\cdots –(m-1,m)$. We will sometimes refer to $S_2$ as a square. Since $S_2$ is connected and contains a unique cycle (induced by its boundary), we have $|E(S_2)|=m^2$. Trivially $S_2$ contains no $S(K_4)$ since $S_2$ contains exactly one cycle, we now generalize $S_2$ to obtain our construction of $S_3\subset P_m^3$, an $S(K_4)$-saturated subgraph of $P_m^3$. We begin with an informal description.

3.1.1. The cross sections

$S_3(1)\subset P_m^3(1)$ and $S_3(m)\subset P_m^3(m)$ are defined as copies of $S_2$; that is we let $S_3(1)=S_2\ast 1$ and $S_3(m)=S_2\ast m$. We link $S_3(1)$ and $S_3(m)$ by a pair of length $m-1$ paths $L^3$ and $R^3$ in $P_m^3$, where $L^3$ (resp. $R^3$) is the shortest path in $P_m^3$ joining $(1,1,1)\in S_3(1)$ to $(1,1,m)\in S_3(m)$ (resp. joining $(m,m,1)\in S_3(1)$ to $(m,m,m)\in S_3(m)$). In fact all edges of of $L^3$ and of $R^3$ are 3-dimensional. Next for each $v\in S_3(1)$ we will define a path $D(v,3)$ of 3-dimensional edges such that the paths $\{D(v,3)\}$ are vertex disjoint and each path $D(v,3)$ is pendant on exactly one point of $S_3(1)\cup S_3(m)$. We the let $S_3=(S_2\ast 1)\cup (S_2\ast m)\cup L^3\cup R^3\cup (\{D(v,3):v\in S_3(1)\})$.

The role of the paths $\{D(v,3)\}$ is to span the gap of vertices lying between $S_3(1)$ and $S_3(m)$; that is, those $v\in P_m^3$ with $2\le v_3\le m-1$, in such a way as to make $S_3$ a connected spanning subgraph of $P_m^3$ while also ensuring that $S_3$ is $S(K_4)$-saturated. In this respect the collection of paths $\{D(v,3)\}$ plays the role in $S_3$ that was played by the set of paths $\{D(v,2)\}\subset S_2$, each path $D(v,2)$ being pendant exactly one point in $S_2(1)\cup S_2(m)$.

Letting $D(3)=(D(2)\ast 1)\cup (D(2)\ast m)\cup (\{D(v,3):v\in S_3(1)\})$, and $S{Q}_3=(S{Q}_2\ast 1)\cup (S{Q}_2\ast m)\cup L^3\cup R^3$, we then have the decomposition $S_3=S{Q}_3\cup D(3)$, in analogy with the formula for $S_2$. We may view $S{Q}_3$ as a “skeleton” of $S_3$ consisting of two cycles and attachment paths $L^3$ and $R^3$. The subgraph $D(3)$ fills in the gap isolated points in $V(P_m^3)–V(S{Q}_3)$, with $D(2)$ doing the filling using dimension 2 edges and $\{D(v,3)\}$ using dimension 3 edges.

3.2. Construction of subgraph $S_3\subset P_m^3$, $m$ even

1. Let $V(S_3)=V(P_m^3)$

2. Let the two cross sections $S_3(1)$ and $S_3(m)$ of $S_3$ be corresponding copies of $S_2$. That is, we let

   $S_3(1)=S_2\ast 1\cong S_2$ and $S_3(m)=S_2\ast m\cong S_2$.

3. Define a ‘left attachment path’ $L^3$ joining $(1,1,1)$ and $(1,1,m)$, and a ‘right attachment path’ $R^3$ joining $(m,m,1)$ and $(m,m,m)$ by

   1. $L^3=(1,1,1)–(1,1,2)–(1,1,3)–\cdots –(1,1,m)$, and

   2. $R^3=(m,m,1)–(m,m,2)–(m,m,3)–\cdots –(m,m,m)$.

4. Let $C_1$ (resp. $C_2$) be the unique cycle of $S_2\ast 1$ (resp. $S_2\ast m$). Then let

   $S{Q}_3=C_1\cup C_2\cup L^3\cup R^3$.

5. (Construction of $D(3)$). Take the unique bipartition of $P_m^3=A\cup B$ for which $(1,1,1)\in A$. For every vertex $v=(a,b,1)\in S_3(1)$ and $w=(c,d,m)\in S_3(m)$, where $$\begin{gathered} v,w\notin X(3)=\{(1,1,1),(m,m,1),(1,1,m), \\ (m,m,m)\} \end{gathered}$$ define the paths $D(v,3)$ and $D(w,3)$ by;

   1. if $v\in A\cap S_3(1)$, then $D(v,3)=(a,b,1)–(a,b,2)–(a,b,3)–\cdots –(a,b,m-1)$,

   2. if $v\in B\cap S_3(1)$, then $D(v,3)=(a,b,2)–(a,b,3)–(a,b,4)–\cdots –(a,b,m)$.

   3. For $w=(c,d,m)\in S_m(3)$, let $D(w,3)=D((c,d,1))$.

   4. Recalling the subgraph $D(2)\subset S_2$, let

      $$D(3)=(D(2)\ast 1)\cup (D(2)\ast m)\cup ({\cup }_{v\in (S_3(1)\cup S_3(m))-X(3)}D(v,3)).$$

6. Define sets $\lambda (3),\rho (3),{\pi }_1(3),{\pi }_2(3)$ by

   $$\begin{array}{rl}\lambda (3)=& \{(1,1,1),(1,1,m)\},\text{the set of `left attachmentpoints' of }{S}_3,\\ \rho (3)=& \{(m,m,1),(m,m,m)\},\text{the set of `rightattachment points' of }{S}_3,\\ {\pi }_L(3)=& \{L^3\},\text{the `left attachment path'of }{S}_3\text{, and}\\ {\pi }_R(3)=& \{R^3\},\text{the `right attachment path'of }{S}_3.\end{array}$$

7. Let $S_3=S{Q}_3\cup D(3)$.

End of construction of $S_3$.

We illustrate the graph $S_3$ in Figure 2.

In that Figure the two large rectangles stand for $S_3(1)$ and $S_3(m)$, each a copy of $S_2\in P_m^2$, as described after the construction of $S_2$. The straight horizontal lines represent rows in $S_3(1)$ and $S_3(m)$. The curved horizontal arcs represent paths $D(v,3)$ in $D(3)$. The darkened points at the ends of the arcs are the endpoints of such a $D(v,3)$, and are either the pair $(i,j,2)$ and $(i,j,m)$ if $(i,j,1)\in B$, or the pair $(i,j,1)$ and $(i,j,m-1)$ if $(i,j,1)\in A$. The open circled points are those immediately preceding or following a path $D(v,3)$ along a nonedge of dimension $3$. For example, the path $D((2,2,1),3)\in D(3)$ begins at the darkened point $(2,2,1)$, passes through the points $(2,2,j)$, $1\le j\le m-1$ in order, and ends at the darkened point $(2,2,m-1)$. Then $D((2,2,1),3)$ is followed by the open circled point $(2,2,m)\in S_3(m)$ joined to $(2,2,m-1)$ by a $3$-dimensional nonedge of $S_3$ in $P_m^3$.

We can now prove $S(K_4)$-saturation for $S_3$. We will say that $H$ is a pendant subgraph in $G$ (or of $G$) if $H$ contains a cutpoint $c$ of $G$ such that $H–c$ is one of the connected components of $G–c$. Thus $H$ is a $c$-component of $G$, and in this case we will also say that $H$ is pendant in $G$ at $c$.

4. $S(K_4)$-saturation in dimension $r\ge 4$

In this subsection we construct an $S(K_4)$-saturated subgraph $S_r$ of $P_m^r$ for $r\ge 4$.

We iterate the previously defined $\ast$ operation. For any vertex $v=(v_1,v_2,\cdots ,v_s)\in P_m^s$, and any fixed $t$-tuple $B=(i_1,i_2,\cdots ,i_t)\in P_m^t$, we let $v\ast B\in P_m^{s+t}=(v_1,v_2,\cdots v_s,i_1,i_2,\cdots ,i_t)$. Then for any subgraph $P\subset P_m^s$, we define the subgraph $P\ast B\subset P_m^{s+t}$ as the subgraph of $P_m^{s+t}$ induced by the vertex set $\{v\ast B:v\in P\}$.

We generalize $S{Q}_3$ to a subgraph $S{Q}_k\subset P_m^k$, $k\ge 3$, which serves as a skeleton of $S_k$, and is defined inductively as follows. Given $S{Q}_k\subset P_m^k$, we let $\underset{\_}{S{Q}_{k+1}}=(S{Q}_k\ast 1)\cup (S{Q}_k\ast m)\cup L^{k+1}\cup R^{k+1}$, where $L^{k+1}\cup R^{k+1}$ are paths linking the two layers $S{Q}_k\ast 1\cong S{Q}_k\ast m\cong S{Q}_k$ given by $L^{k+1}=1^{k+1}–1^{k}2–1^{k}3–\cdots –1^{k}m$, and $R^{k+1}=m^{k}1–m^{k}2–m^{k}3–\cdots –m^{k+1}$. Let $X(k+1)$ be the four endpoints of these two paths; that is, $\underset{\_}{X(k+1)}=\{1^{k+1},1^{k}m,m^{k}1,m^{k+1}\}$. Note then that $S{Q}_k$ contains $2^{k-2}$ squares, linked inductively by sets of paths $\{L^j,R^j\}$, at dimensions $3\le j\le k$. We will see that the skeleton $S{Q}_k\subset S_k$ is $S(K_4)$-free. But it is not $S(K_4)$-saturated because of the gap of points $z\in P_m^k$ at dimension $k$ lying between $S{Q}_k(1)$ and $S{Q}_k(m)$; that is, points with $1<z_k<m$, these being are isolated in $S{Q}_k$. Here we note the role of the set $X(k)$ as an exception. That is, for the endpoints of $L^k$ and $R^k$, $\{1^k,1^{k-1}m\}$ and $\{m^{k-1}1,m^k\}$ respectively, there is no such gap, since every point on the shortest path joining each of these pairs is already included in $S{Q}_k$ on either the path $L^k$ or $R^k$. For all other pairs $u\in S{Q}_k(1)$, $u^{\prime }\in S{Q}_k(m)$ differing only in their $k$’th coordinate with values $u_k=1$ and $u_k^{\prime }=m$, this gap will be filled by a path $D(u,k)$ generalizing $D(u,3)$. We describe $D(u,k)$ informally below, before presenting its formal construction, as part of the inductive construction of $S_r$, $r\ge 4$.

First we will need additional notation. Take a point $v=(v_1,v_2,\cdots ,v_{k-1},1)\in P_m^k(1)$, and let $v^{\prime }=(v_1,v_2,\cdots ,v_{k-1},m)\in P_m^k(m)$ be its corresponding point in $P_m^k(m)$. Now define two paths $\underset{\_}{{\mathcal{P}}_1(k,v,v^{\prime })}$ and $\underset{\_}{{\mathcal{P}}_m(k,v,v^{\prime })}$ by

$$\begin{array}{rl}{\mathcal{P}}_1(k,v,v^{\prime })=& v–(v_1,v_2,\cdots ,v_{k-1},1)–(v_1,v_2,\cdots ,v_{k-1},2)–\cdots –(v_1,v_2,\cdots ,v_{k-1},m-1),\end{array}$$ and $$\begin{array}{rl}{\mathcal{P}}_m(k,v,v^{\prime })=& (v_1,v_2,\cdots ,v_{k-1},2)–(v_1,v_2,\cdots ,v_{k-1},3)–\cdots –(v_1,v_2,\cdots ,v_{k-1},m-1)–v^{\prime }.\end{array}$$

For each such pair $v,v^{\prime }\notin X(k)$ we will choose $D(v,k)$ to be one of the paths $\{{\mathcal{P}}_1(k,v,v^{\prime }),{\mathcal{P}}_m(k,v,v^{\prime })\}$, the choice based on a bipartition of $P_m^k$. We then let $D(v^{\prime },k)=D(v,k)$. Now let $\underset{\_}{head(D(v,k))}$ (resp. $\underset{\_}{tail(D(v,k))}$ be whichever of $v$ or $v^{\prime }$ is (resp. is not) on $D(v,k)$. For example, in Figure 2 illustrating $S_3$, we have $head(D((2,2,1),3))=(2,2,1)$ while $tail(D((2,2,1),3))=(2,2,m)$, and $head(D((2,1,1),3))=(2,1,m)$ while $tail(D((2,1,1),3))=(2,1,1)$. So one of $$\begin{gathered} \{head(D(v,k)),tail(D( \\ v,k))\} \end{gathered}$$ is in $P_m^k(1)$ while the other is in $P_m^k(m)$. The paths $D(v,k)=D(v^{\prime },k)$ “fill in” the gap in $S{Q}_k$ of points in $P_m^k\mathrm{\setminus }S{Q}_k$ lying on the shortest path in $P_m^k$ between $v$ and $v^{\prime }$, and are the analogues of the paths $D(v,3)$ in the construction of $S_3$.

We also let ${\mathcal{P}}_1(k,v,v^{\prime }{)}^R={\mathcal{P}}_m(k,v,v^{\prime })$ and ${\mathcal{P}}_m(k,v,v^{\prime }{)}^R={\mathcal{P}}_1(k,v,v^{\prime })$. Recalling the $\ast$ operation defined earlier in this section, we have isomorphic copies of the paths ${\mathcal{P}}_1(k,v,v^{\prime })$ and ${\mathcal{P}}_1(k,v,v^{\prime }{)}^R$ in $P_m^{k+1}$ given by ${\mathcal{P}}_1(k,v,v^{\prime })\ast i$ and $({\mathcal{P}}_1(k,v,v^{\prime })\ast i{)}^R$ for $1\le i\le m$, the latter defined by ${\mathcal{P}}_1(k,v,v^{\prime }{)}^R\ast i$. Iteratively for any $(r-k)$-tuple $B_{r-k}$ with entries from $\{1,m\}$, we also have ${\mathcal{P}}_1(k,v,v^{\prime })\ast B\subset P_m^r$ and similarly for ${\mathcal{P}}_1(k,v,v^{\prime })\ast B\subset P_m^r$. Further for any set $T$ of paths of the form $D(v,k)$ or $D(v,k{)}^R$ (over various $v$ and $k$), $k\ge 3$, we let $\underset{\_}{T^R}=\{D(v,k{)}^R:D(v,k)\in T\}\cup \{D(v,k):D(v,k{)}^R\in T\}$.

As remarked above the paths $D(v,k)$ fill in gap in $S{Q}_k$ at dimension $k$. The paths $D(v,k)$ are “lifted” to isomorphic copies of themselves in $S_r\subset P_m^r$ by iterated applications of the $\ast$ operation. Now $D(r)$ will be the collection of these lifted paths $D(v,k)$, $3\le k\le r$, defined inductively by $D(r+1)=(D(r)\ast 1)\cup (D(r{)}^R\ast m)\cup ({\cup }_{v\in P_m^r(1)\cup P_m^r(m)-X(r+1)}D(v,r+1))$. The collection of paths $D(r+1)$ “fills in” the previously described gaps of isolated points in $S{Q}_k$, in all dimensions $k$, $3\le k\le r+1$. With this inductive definition of $D(r)$ we finally take $S_r=S{Q}_r\cup D(r)$.

Throughout the remainder of this section we shall occasionally use the symbol $[1{]}_r$ (resp. $[m{]}_r$) as an abbreviation for $S_r(1)$ (resp. $S_r(m)$).

4.1. Construction of $S(K_4)$-saturated subgraph $S_r\subset P_m^r$ for $r\ge 4$

1. (Initialization) Construct subgraphs $S_3\subset P_m^2$ (given in section 3 ), $D(3)\subset S_3$, and $S{Q}_3\subset S_3$ given by $$D(3)=(D(2)\ast 1)\cup (D(2)\ast 1)\cup \{D(v,3):v\in P_m^3(1)\cup P_m^3(m)–\{1^3,1^{2}m,m^{2}1,m^3\}\}$$ (with $D(v,3)$ defined in section 3), $S{Q}_3$ as defined in step 4 of the construction of $S_3$.

2. For $r\ge 3$ assume subgraphs $D(r),S{Q}_r\subset P_m^r$, sets of paths ${\pi }_L(r),{\pi }_R(r)\subset P_m^r$, and sets of attachment points $\lambda (r)\cup \rho (r)$ have been constructed.

3. Define attachment paths and attachment points in $S{Q}_{r+1}\subset P_m^{r+1}$ by

   1. the left attachment point $L(S_{r+1})=1^{r+1}$, and right attachment point $R(S_{r+1})=m^{r+1}$

   2. attachment paths given by

   1. left attachment path $L^{r+1}=1^{r+1}–1^{r}2–1^{r}3–\cdots –1^{r}m$, and

   2. right attachment path $R^{r+1}=m^{r}1–m^{r}2–m^{r}3–\cdots –m^{r+1}$

4. Define sets of attachment points and sets of attachment paths in $S{Q}_{r+1}$ by

   1. $\lambda (r+1)=(\lambda (r)\ast 1)\cup (\lambda (r)\ast m)\cup \{L(S_{r+1})\}$ (set of left attachment points in $S{Q}_{r+1}$)

   2. $\rho (r+1)=(\rho (r)\ast 1)\cup (\rho (r)\ast m)\cup \{R(S_{r+1})\}$ (set of right attachment points in $S{Q}_{r+1}$)

   3. ${\pi }_L(r+1)=({\pi }_L(r)\ast 1)\cup ({\pi }_L(r)\ast m)\cup \{L^{r+1}\}$ (set of left attachment paths in $S{Q}_{r+1}$)

   4. ${\pi }_R(r+1)=({\pi }_R(r)\ast 1)\cup ({\pi }_R(r)\ast m)\cup \{R^{r+1}\}$ (set of right attachment paths in $S{Q}_{r+1}$)

5. Let $V(S_{r+1})=P_m^{r+1}$, and take the unique bipartition $A_{r+1}\cup B_{r+1}$ of $P_m^{r+1}$ for which $1^{r+1}\in A_{r+1}$.

6. (Construction of paths $D(v,r+1)$). Consider any corresponding pair $v\in [1{]}_{r+1}$ and $v^{\prime }\in [m{]}_{r+1}$ (that is, $v_j=v_j^{\prime }$ for $1\le j\le r$ and $v_{r+1}=1,v_{r+1}^{\prime }=m$), satisfying $$\begin{gathered} v,v^{\prime }\notin \{L([1{]}_{r+1}),L([m{]}_{r+1}),R \\ ([1{]}_{r+1}),R([m{]}_{r+1})\}=\{1^{r+1},1^{r}m,m^{r}1,m^{r+1}\} \end{gathered}$$,

   Noting that $v\in A_{r+1}\iff v^{\prime }\in B_{r+1}$, define paths $D(v,r+1)$ by

   1. If $v\in A_{r+1}\cap P_m^{r+1}(1)$, then $D(v,r+1)={\mathcal{P}}_1(r+1,v,v^{\prime })$

   2. If $v\in B_{r+1}\cap P_m^{r+1}(1)$, then $D(v,r+1)={\mathcal{P}}_m(r+1,v,v^{\prime })$

   3. $D(v^{\prime },r+1)=D(v,r+1)$.

7. (Construction of $D(r+1)$). $$D(r+1)=(D(r)\ast 1)\cup (D(r{)}^R\ast m)\cup ({\cup }_{v\in P_m^{r+1}(1)\cup P_m^{r+1}(m)-X(r+1)}D(v,r+1)),$$ where $\underset{\_}{X(r+1)}=\{1^{r+1},1^{r}m,m^{r}1,m^{r+1}\}$.

8. (Construction of $S{Q}_{r+1}$). $$S{Q}_{r+1}=(S{Q}_r\ast 1)\cup (S{Q}_r\ast m)\cup L^{r+1}\cup R^{r+1}$$

9. Let $S_{r+1}=S{Q}_{r+1}\cup D(r+1)$.

   (End of construction).

In Figure 4 we illustrate the inductive construction of $S_{r+1}$, omitting the set of paths $D(r+1)$ in order to simplify the illustration. The two copies of $S_r$ (namely $S_{r+1}(1)$ and $S_{r+1}(m)$) are encircled by large by dotted ovals, and joined by the paths $L^{r+1}$ and $R^{r+1}$. The eight boxes each represent a copy of $S_{r-2}$. The four horizontally close pairs of these boxes, together with paths $L^{r-1}\ast B$ and $R^{r-1}\ast B$, each form a copy of $S_{r-1}$, where $B$ is a string of length $2$ over the letters $\{1,m\}$ that depends on the pair. The top two copies of $S_{r-1}$ (i.e. within $S_{r+1}(1)$), together with the paths $L^r\ast 1$ and $R^r\ast 1$, form the copy of $S_r\cong S_{r+1}(1)$, while the bottom two copies of $S_{r-1}$ together with the paths $L^r\ast m$ and $R^r\ast m$ for the copy of $S_r\cong S_{r+1}(m)$.

The $\ast$ and $D(r{)}^R$ notation used above are iterated in the natural way. For example, if $B$ and $C$ are strings over the letters $1$ and $m$, then $(D(r)\ast B)\ast C=D(r)\ast BC$. Also we have $(D(r)\ast B{)}^R=D(r{)}^R\ast B$, $(D(r{)}^R{)}^R=D(r)$, and $(D_1\cup D_2{)}^R=D_1^R\cup D_2^R$ where $D_i$, $i=1,2$ are each $D(r)$ or $D(r{)}^R$.

We can decompose $S_{r+1}$ as follows. Let $\underset{\_}{E_{r+1}}={\cup }_{v\in S_{r+1}(1)-X(r+1)}D(v,r+1)$, we have $S_{r+1}=S_{r+1}(1)\cup S_{r+1}(m)\cup E_{r+1}\cup L^{r+1}\cup R^{r+1}=((S{Q}_r\cup D(r))\ast 1)\cup ((S{Q}_r\cup D(r{)}^R)\ast m)\cup E_{r+1}\cup L^{r+1}\cup R^{r+1}$.

For the first component on the right we have $(S{Q}_r\cup D(r))\ast 1=S_r\ast 1$, giving us a copy of $S_r$. We now show that the second component is also isomorphic to a copy of $S_r$, which reduces to showing $S{Q}_r\cup D(r{)}^R\cong S_r$. First note that by step $7$ of the construction we have $D_r^R=(D(r-1{)}^R\ast 1)\cup (D(r-1)\ast m)\cup E_r^R$. Therefore we have $$S{Q}_r\cup D(r{)}^R=((S{Q}_{r-1}\cup D(r-1{)}^R)\ast 1)\cup ((S{Q}_{r-1}\cup D(r-1))\ast m)\cup L^r\cup R^r\cup E_r^R.$$ Similarly $$S{Q}_r\cup D(r)=((S{Q}_{r-1}\cup D(r-1))\ast 1)\cup ((S{Q}_{r-1}\cup D(r-1{)}^R)\ast m)\cup L^r\cup R^r\cup E_r.$$

We can now construct an isomorphism $f:S{Q}_r\cup D(r{)}^R\to S{Q}_r\cup D(r)$ which is a reflection in the $r$’th coordinate. Take $x\in S{Q}_r\cup D(r{)}^R$, so $x=(x_1,x_2,\cdots ,x_{r-1},j)$ with $1\le j\le m$. Then define $f(x)=(x_1,x_2,\cdots ,x_{r-1},m–j+1)$. Observe that since $f$ leaves the first $r-1$ coordinates undisturbed, we have $f((S{Q}_{r-1}\cup D(r-1{)}^R)\ast 1)=(S{Q}_{r-1}\cup D(r-1{)}^R)\ast m$ and $f((S{Q}_{r-1}\cup D(r-1))\ast m)=(S{Q}_{r-1}\cup D(r-1))\ast 1$. By this reflection action in the $r$’th coordinate, we see that $f$ reflects the paths $L^r$ and $R^r$ about their midpoints, so that $f(L^r)=L^r$ and $f(R^r)=R^r$. By the same reflection we see that for any path $D(v,r{)}^R\in E_r^R$, $f(D(v,r{)}^R)=D(v,r)\in E_r$, and that $f$ is then a bijection between $E_r^R$ and $E_r$ sending each path $D(v,r{)}^R$ to its reflection $D(v,r)$. It follows that $f(S{Q}_r\cup D(r{)}^R)=S{Q}_r\cup D(r)$ using the decompositions of $S{Q}_r\cup D(r{)}^R$ and $S{Q}_r\cup D(r)$ in the preceding paragraph.

The fact that $f$ is a graph isomorphism is straightforward from its reflection property. We argue just a few typical cases here. For any $x\in S{Q}_r\cup D(r{)}^R$, write $x=v_x\ast j$, $1\le j\le m$ with $v_x=(x_1,x_2,\cdots ,x_{r-1})$. First take an edge $xy\in E(L^r\cup R^r\cup E_r^R)$. Then $x=v_x\ast j$ and $y=v_x\ast (j+1)$, the case $y=v_x\ast (j-1)$ being similar, and noting that $v_x=v_y$. Then $f(x)=v_x\ast (m-j+1)$ and $f(y)=v_x\ast (m-j)$. This shows that if $xy\in E(L^r)$ then $f(x)f(y)\in E(L^r)$, and the same statement with $R^r$ in place of $L^r$. It also shows that if $xy\in E_r^R$, say with $xy\in E(D(v,r{)}^R)\subset E(E_r^R)$, then $f(x)f(y)\in E(D(v,r))\subset E(E_r)$. Thus in the case $xy\in E(L^r\cup R^r\cup E_r^R)\subset E(S{Q}_r\cup D(r{)}^R)$ we have $f(x)f(y)\in E(L^r\cup R^r\cup E_r)\subset E(S{Q}_r\cup D(r))$. As another case suppose $xy\in E(S{Q}_{r-1}\cup D(r-1{)}^R)\ast 1)$, so $x=v_x\ast 1$ and $y=v_y\ast 1$ and $v_x{v}_y\in E(S{Q}_{r-1}\cup D(r-1{)}^R)$. Then $f(x)f(y)=(v_x\ast m)(v_y\ast m)\in E(S{Q}_{r-1}\cup D(r-1{)}^R)\ast m)$. A similar argument shows that $f$ preserves edges in $S{Q}_{r-1}\cup D(r-1))\ast m$.

We now outline briefly how $f$ preserves nonedges of $S{Q}_r\cup D(r{)}^R$ in $P_m^r$. For brevity let $$B(r)=((S{Q}_{r-1}\cup D(r-1{)}^R)\ast 1)\cup ((S{Q}_{r-1}\cup D(r-1))\ast m).$$

Nearly the identical proof given for edges shows that $f$ preserves nonedges of $S{Q}_r\cup D(r{)}^R$ in $P_m^r$ lying in $B(r)$, based again on the reflection of $f$. We consider in detail one different case; that is, where a nonedge $xy$ of $S{Q}_r\cup D(r{)}^R$ satisfies $x\in B(r)$ and $y\notin B(r)$. In this case, $xy$ is the $r$-dimensional nonedge immediately following or preceding a path $D(w,r{)}^R$. We can take by symmetry $x=v_x\ast m\in (S{Q}_{r-1}\cup D(r-1))\ast m$ and $y=v_y\ast (m-1)$, with $v_x=v_y=(x_1,x_2,\cdots ,x_{r-1})$. Then $f(x)f(y)=(v_x\ast 1)(v_x\ast 2)$ which is a nonedge in $S{Q}_r\cup D(r)$. The remaining cases of nonedges $xy$ satisfy $xy\in L^r\cup R^r\cup E_r^R$, whose details we omit. The proof that $f(x)f(y)$ is a nonedge $S{Q}_r\cup D(r)$ relies on the nonexistence of any edge in $S_r$ with one end in each of two distinct paths $D(w,r)$ and $D(w^{\prime },r)$, or one end in $L^r\cup R^r$ and the other in some path $D(w,r)$.

So our decomposition shows that $S_{r+1}$ decomposes into two copies of $S_r$ (the subgraphs $S_{r+1}(1)$ and $S_{r+1}(m)$), joined by paths $L^{r+1}$ and $R^{r+1}$, together with the subgraph $E_{r+1}$. Further, $E_{r+1}$ is a vertex disjoint collection of paths of the form $D(v,r+1)$, where each such path is pendant on exactly one of $S_{r+1}(1)$ or $S_{r+1}(m)$. This is illustrated in Figure 7.

As examples of the $\lambda$ and $\rho$ sets, we gave $\lambda (3)$ and $\rho (3)$ in step $6$ of the construction of $S_3$ in the preceding subsection. We also have $$\lambda (4)=\{(1,1,1,1),(1,1,m,1),(1,1,1,m),(1,1,m,m)\},$$ and $$\rho (4)=\{(m,m,1,1),(m,m,m,1),(m,m,1,m),(m,m,m,m)\}.$$

Our goal now is to show that $S_r$ is an $S(K_4)$-saturated subgraph of $P_m^r$. As our first step, we will show that $S_r$ contains no $S(K_4)$. For this, we first reduce to showing that the subgraph $S{Q}_r$ of $S_r$ contains no $S(K_4)$. We let $\underset{\_}{[D(r)]}$ be the subgraph of $S_r$ induced by $V(D(r))$. We call the vertices of $[D(r)]$ connection points of $S_r$, and we call any path in $[D(r)]$ a connection path of $S_r$. We examine $[D(r)]$ for $r\ge 3$ in the Lemma which follows.

For the structure of $D(r)$, observe first that $D(2)$ is a disjoint union of paths of the form $D(v,2)$. We have previously observed in the proof of Theorem 3.1 that $D(3)$ is a forest each tree component of which is a path or a comb; the latter being a tree $T$ containing a path $P$ such that $T-E(P)$ is a disjoint union of paths, and of course a path being a special case of a comb. The path $P$ in these nonpath combs $T$ is a path $D(v,2)$ for some $v$. This can be seen in Figure 2, where the path $(2,1,1)\cdots (2,1,m-1)$ plays the role of $P$ and union of paths $D(v,3)$, $v\in P$ and $v=head(D(v,3))$, together with $P$ form a tree component which is a comb. For $D(4)$, the tree components $T$ are either trees containing a path $P$ for for which each component of $T-E(P)$ is a comb, or just paths paths $D(v,4)$ (for example $D((m-1,1,1,1),4))$. For general $D(k)$, each tree component is a nested sequence (in the sense above) of combs up to depth $k-2$, though we do not use this fact.

In light of Lemma 4.1, for any $v\in [D(r)]$, let $T(v)$ be the tree component of $[D(r)]$ containing $v$. Then let $\underset{\_}{Source(v)}$ be the point of $S{Q}_r$ at which $T(v)$ is pendant. As an example, we refer back to Figure 2 and the tree $H=P\cup ({\cup }_{v\in P}D(v,3))$, where $P=(2,1,1)\cdots (2,1,m-1)$ is the path given in the above paragraph. This $H$ is a tree component of the forest $D(3)$, and is pendant in $S_3$ at the point $(2,1,1)$. So for every vertex $x\in H$ we have $Source(x)=(2,1,1)$. In particular we also have $Source((2,2,j)=(2,1,1)$ for $1\le j\le m-1$ and generally for each $1\le k\le m-1$ we have $Source((2,k,j)=(2,1,1)$, $1\le j\le m-1$.

The arguments in the rest of this section will be inductive, and to facilitate these we introduce here some abbreviated notation for referring to substructures of $S_{r+1}$.

1. Since $r+1$ will be fixed, we will abbreviate $[1{]}_{r+1}$ and $[m{]}_{r+1}$ to $[1]$ and $[m]$ respectively. So $[1]$ (resp. $[m]$) denotes the subgraph $S_{r+1}(1)$ (resp. $S_{r+1}(m)$) of $S_{r+1}$, this being the subgraph of $S_{r+1}$ induced by points $v$ for which $v_{r+1}=1$ (resp. $v_{r+1}=m$). We let $\underset{\_}{[11]}$ and $\underset{\_}{[1m]}$ be the subgraphs of $S_{r+1}(1)=[1]$ induced by points $v$ satisfying $v_r=1$ and $v_r=m$ respectively, and similarly let $\underset{\_}{[m1]}$ and $\underset{\_}{[mm]}$ be the subgraphs of $S_{r+1}(m)=[m]$ induced by points $v$ satisfying $v_r=1$ and $v_r=m$ respectively. So altogether we have $[1]\cong [m]\cong S_r$, while $[ij]\cong S_{r-1}$ for $i,j\in \{1,m\}$.

2. The left and right attachment point and path structure is naturally inherited by $[m]$ and $[1]$ as copies of $S_r$ in $S_{r+1}$, and their subgraphs $[11],[1m]$ etc. as copies of $S_{r-1}$ in $S_{r+1}$. The coordinates in $S_{r+1}$ of such points are obtained by taking the coordinates of the attachment point in $S_r$ (or $S_{r-1}$) and appending the appropriate coordinate suffix in $S_{r+1}$. So we have $$\begin{array}{rl}L([1])=& 1^{r}1=1^{r+1}=L(S_{r+1}),\\ R([1])=& m^{r}1,\\ L([m])=& 1^{r}m,\\ R([m])=& m^{r}m=m^{r+1}=R(S_{r+1}),\end{array}$$ and for $i,j=1$ or $m$ we have $$\begin{array}{rl}L([ij])=& 1^{r-1}ji,\end{array}$$ and $R([ij])=m^{r-1}ji.$ So we have $$\begin{array}{rl}L([11])=& L([1]),\\ R([11])=& m^{r-1}11=m^{r-1}{1}^2,\\ L([1m])=& 1^{r-1}m1,\\ R([1m])=& m^{r-1}m1=m^{r}1,\\ L([m1])=& 1^{r-1}1m=1^{r}m,\\ R([m1])=& m^{r-1}1m,\\ L([mm])=& 1^{r-1}mm=1^{r-1}{m}^2,\end{array}$$ and $$\begin{array}{rl}R([mm])=& m^{r-1}mm=m^{r+1}=R(S_{r+1}).\end{array}$$

Similarly the attachment paths $L^r$ and $R^r$ in $S_r$ appearing in the copy $S_{r+1}(1)\cong S_r$ (resp. $S_{r+1}(m)\cong S_r$ of $S_r$ will be written as $L^r\ast 1$ and $R^r\ast 1$ (resp. $L^r\ast m$ and $R^r\ast m$) as in step $4$ of the construction of $S_r$.

The various left and right attachment paths, all of length $m-1$, join pairs of these attachment points. For example, $L^{r+1}$ joins $L([11])$ to $L([m1])$, and $R^{r+1}$ joins $R([1m])$ to $R([mm])$. Now let $L^r([i])=L^r\ast i$ and $R^r([i])\ast i$ be the left and right attachment paths in $[i]$, $i=1,m$. Then $L^r([i])$ joins $L([i1])$ to $L([im])$, and $R^r([i])$ joins $R([i1])$ to $R([im])$.

Toward showing that $S_r$ is $S(K_4)$-saturated in $P_m^r$ we begin by proving that $S_r$ contains no $S(K_4)$. Recall that the points of degree $3$ in an $S(K_4)$ are called junction points or just junctions, and we call the six internally disjoint paths in this $S(K_4)$ joining the pairs of junctions junction paths.

To complete the proof that $S_r$ is $S(K_4)$-saturated in $P_m^r$, it remains to prove the nonedge addition property. To that end, we will need a Lemma on the path structure in $S_r$.

Figure 4 illustrates concatenations of left and right attachment paths (in bold and dashed curves) claimed to exist in parts a) and b) of this Lemma. For a concatenation of left attachment paths from $L(S_{r+1})$ to $L(S_2)$ ( as in part a) ) observe the sequence of paths starting at the upper left corner which is the vertex $L(S_{r+1})$. One such concatenation begins with the left attachment path $L^{r-1}\ast 1\ast 1$ followed by a an inductively constructed concatenation of such paths (indicated by the oblique line) within the upper and second from left copy of $S_{r-2}$ ending at the vertex $L(S_2)$ of the $S_2$ within that copy of $S_{r-2}$ in the figure. Another example again begins at $L(S_{r+1})$, and proceeds along the left attachment paths in the order $L^{r+1}–L^r\ast m–L^{r-1}\ast m\ast m$ and finally along a an inductively constructed concatenation of left attachment paths (again shown as an oblique line) within the lower and rightmost copy of $S_{r-2}$, leading to $L(S_2)$. Finally observe the concatenation of right and left attachment paths going from $R(S_{r+1})$ (the corner point at lower right) to $L(S_{r+1})$ (the corner point at upper left) as in part b) of the Lemma. This begins with the succession of two right attachment paths $R^{r+1}–R^r\ast 1$ followed by the inductively constructed concatenation of right attachment paths within the upper second from left copy of $S_{r-2}$, leading to $R(S_2)$ (all in dashed curves), followed by the cycle around $S_2$, followed by the reverse of the concatenation of the first two left attachment paths given in the first example, leading to $L(S_{r+1})$.

In our next theorem we show that the edge addition property holds in $S_r$; that is, that for any nonedge $e$ of $S_r$ in $P_m^r$ we have $S(K_4)\subset S_r+e$. The proof will be by induction on $r$, and to facilitate that induction we need the following definitions and notation.

We continue with the notation $A\stackrel{\text{S}}{\to }B$ and its concatenation used previously in the analysis of $S_3$. We extend here the meaning of symbol $S$ to include not only the name of a path joining vertices $A$ and $B$, but also the name of a Lemma or construction justifying the existence of such a path. So $S$ can take values $La,Lb,Lc,Ld$ to indicate Lemma 4.9 parts $a,b,c,d$ respectively, or $L^{\prime }a,L^{\prime }b$ to indicate Corollary 4.2 parts $a,b$ respectively, or just the name of some path – usually some attachment path such as $L^{r+1}$, $L^r\ast 1\subset [1]$, or $L^r\ast m\subset [m]$.

5. Conclusions

In this paper we studied the saturation function $Sat(P_m^r,S(K_4))$; that is, the minimum number of edges in any $S(K_4)$ saturated spanning subgraph of the $r$-dimensional grid $P_m^r$. Here $S(K_4)$ is the graph family of all subdivisions of the complete graph $K_4$. In dimension 2 we obtained the exact result $Sat(P_m\times P_n,S(K_4))=mn+1$ if at least one of $m$ or $n$ is odd with $m\ge 5$ and $n\ge 5$. In dimension 3 we found the near exact result $m^3+1\le Sat(P_m^3,S(K_4))\le m^3+2$ for $m$ even with $m\ge 4$. For arbitrary $r\ge 3$ with $m$ even and $m\ge 4$, we proved that $Sat(P_m^r,S(K_4))\le m^r+2^{r-1}–2$.

The upper bounds for dimension $r\ge 3$ were obtained by the inductive construction of the $S(K_4)$-saturated graph $S_r\subseteq P_m^r$ described in the paper.

6. Appendix I – independence of paths

In this Appendix we prove independence of the three paths $P_1,P_2,P_3$ used in the construction of an $S(K_4)$ in the proof of Theorem 4.10, in the case $k=r+1$ and $Source(w)\in [1m]$.

First we show that $P_1\cap W=\{q(Source(v))\}$. The initial subpath of $P_1$ satisfies $W\cap (R([mm])\stackrel{R^r\ast m}{\to }R([m1]))=\mathrm{\varnothing }$. The remaining succession of paths on $P_1$, which we call $Q$, satisfies $Q=R([m1])\stackrel{\text{La}}{\to }R(S_2(Source(v)))\stackrel{\text{Ld}}{\to }q(Source(v))$ lies in $[m1]$. So it remains to show that $Q\cap W\cap [m1]=\{q(Source(v))\}$. The subpath $Q^{\prime }=R([m1])\stackrel{\text{La}}{\to }R(S_2(Source(v)))$ of $Q$ is a right attachment path. But $W\cap [m1]$ consists of a left attachment path (so it has empty intersection with $Q^{\prime }$), a path in $S_2(Source(v))$ avoiding $R(S_2(Source(v)))$ (so having empty intersection with $Q^{\prime }$), and finally a connection path $Source(v)\stackrel{\text{L'b}}{\to }v$ which must have empty intersection with $Q^{\prime }$ since $Q^{\prime }$ contains no connection points and does not contain $Source(v)$. We see that the subpath $Q^{″}=R(S_2(Source(v)))\stackrel{\text{Ld}}{\to }q(Source(v))$ of $Q$ lies in $S_2(Source(v))$. But then Lemma 4.9c,d give that $Q^{″}\cap (W\cap S_2(Source(v)))=\{q(Source(v))\}$. So we get $Q\cap W\cap [m1]=\{q(Source(v))\}$ as desired.

Next we show that $P_2\cap W=\{L([m1])\}$. Since $W\cap [mm]=\mathrm{\varnothing }$, the initial subpath $R([mm])\stackrel{\text{Lb}}{\to }L([mm])$ of $P_2$ has empty intersection with $W$. The second subpath $L([mm])\stackrel{L^r\ast m}{\to }L([m1])$ of $P_2$ intersects $W$ at the vertex $L([m1])$ by construction. Hence $P_2\cap W=\{L([m1])\}$ as required.

Now we show that $P_3\cap W=\{q(Source(w))\}$. Here the proof is similar to the one given for showing $P_1\cap W=\{q(Source(v))\}$. First observe that the initial subpath $R([mm])\stackrel{R^{r+1}}{\to }R([1m])$ has empty intersection with $W$ by construction. The rest of $P_3$ lies in $[1m]$, so it suffices to show that $P_3\cap W\cap [1m]=\{q(Source(w))\}$. By construction $W\cap [1m]=Source(w)\stackrel{\text{: Lc :}}{\to }L(S_2(Source(w)))\stackrel{\text{La}}{\to }L([10])$. Suppose first that $Source(w)\ne L(S_2(Source(w)))$. Then the subpath. $\lambda =L(S_2(Source(w)))\stackrel{\text{La}}{\to }L([1m])$ of $W\cap [m1]$ has empty intersection with $P_3\cap [1m]$, since $\lambda$ is a left attachment path while $P_3\cap [1m]$ is a right attachment path followed by a path $R(S_2(Source(w)))\stackrel{\text{Ld}}{\to }q(Source(w))$ not containing $L(S_2(Source(w)))$. It then remains to observe that the subpath $Source(w)\stackrel{\text{: Lc :}}{\to }L(S_2(Source(w)))$ intersects the subpath $R(S_2(Source(w)))\stackrel{\text{Ld}}{\to }q(Source(w))$ at $q(Source(w))$ by Lemma 4.9c,d, showing that $P_3\cap W\cap [1m]=\{q(Source(w))\}$ as desired. Now suppose that $Source(w)=L(S_2(Source(w)))$. The we have $Source(w)=q(Source(w))$. So the path $R(S_2(Source(w)))\stackrel{\text{Ld}}{\to }q(Source(w))$ on $P_3$ reaches $L(S_2(Source(w)))=q(Source(w))$, and again we get $P_3\cap W\cap [1m]=\{q(Source(w))\}$.

To complete the proof of independence of the three paths, we show that $P_1\cap P_2\cap P_3=\{R([mm])\}$, where the containment $R([mm])\in P_1\cap P_2\cap P_3$ is clear by definition. We easily have $P_3\cap (P_1\cup P_2)=\{R([mm])\}$, since $P_1\cup P_2\subset [m]$, while $P_3\cap [m]=\{R([mm])\}$. As for $P_1\cap P_2$, since $P_1\cup P_2\subset [m]$ and since neither $P_1$ nor $P_2$ contain connection points of $[m]$, it suffices to show that $P_1\cap P_2\cap [mm]=\{R([mm])\}$ and $P_1\cap P_2\cap [m1]=\mathrm{\varnothing }$. The first claim is clear since by definition $P_1\cap [mm]=\{R([mm])\}$. For the second claim, we note that $P_2\cap [m1]=\{L([m1])\}$. But $P_2\cap [m1]$ is a right attachment path, which therefore cannot contain $L([m1])$, followed by a path internal to $S_2(Source(v))$ which avoids $L(S_2(Source(v)))$ by Lemma 4.9d. So we obtain $P_1\cap P_2\cap [m1]=\mathrm{\varnothing }$, and it follows that $P_1\cap P_2\cap P_3=\{R([mm])\}$, yielding the independence of the three paths $P_i$, $1\le i\le 3$.

7. Appendix II – completion of proof of theorem 4.10

In this Appendix we complete the proof of Theorem 4.10 by providing the details for the case $k\le r$, where the nonedge $vw$ being added to $S_{r+1}$ has dimension $k$ in $P_m^{r+1}$. The case $k=r+1$ in the proof of Theorem 4.10 was treated in the main body of the paper.

First we can reduce to the case where $\{v,w\}\cap ([m]\cup [1])=\mathrm{\varnothing }$. Suppose not. If exactly one of $v$ or $w$ is in $[m]\cup [1]$, then $vw$ is an $(r+1)$-dimensional nonedge following or preceding some path $D(v^{\prime },r+1)$, a contradiction to $k\le r$. If $v\in [m]$ and $w\in [1]$, then $v_{r+1}=m$ and $w_{r+1}=1$, showing that $v$ and $w$ disagree (in fact by more than $1$) in the $(r+1)$’st coordinate, so contradicting $k\le r$. Finally with either $\{v,w\}\subset [m]$ or $\{v,w\}\subset [1]$, then induction immediately gives an $S(K_4)$ in either $[m]+vw$ or $[1]+vw$ and therefore in $S_{r+1}+vw$, as required.

From $\{v,w\}\cap ([m]\cup [1])=\mathrm{\varnothing }$ it follows from the decomposition of $S_{r+1}$ at the beginning of the proof that $\{v,w\}\subset D(r+1)\cup L^{r+1}\cup R^{r+1}$. We cannot have $\{v,w\}\subset L^{r+1}\cup R^{r+1}$ since neither $L^{r+1}$ nor $R^{r+1}$ contain nonedges of $P_m^{r+1}$, while points of $L^{r+1}$ differ from points of $R^{r+1}$ in more than one coordinate. Recalling the notation $D^{\prime }(r+1)=D(r+1)–([1]\cup [m])$ we must have either

1. both $v$ and $w$ in $[D^{\prime }(r+1)]$, or

2. one of $\{v,w\}$ in $L^{r+1}\cup R^{r+1}$ while the other is in $[D^{\prime }(r+1)]$.

We begin by assuming $k=r$, and later consider the case $k<r$.

Suppose first that $v,w\in [D^{\prime }(r+1)]$ as in case $(A)$, and we treat the case $(B)$ afterwards. Since $k=r$, then $v$ and $w$ are on distinct $D$-paths in dimension $r+1$, say $v\in D(v^{\prime },r+1)$ and $w\in D(w^{\prime },r+1)$, since otherwise $v$ and $w$ would disagree in coordinate $r+1$, contrary to $k=r$. By possibly renaming we can suppose $v^{\prime },w^{\prime }\in [m]$. Now $v$ (resp. $w$) disagrees with $v^{\prime }$ (resp. $w^{\prime }$) only in the $(r+1)$’st coordinate, but $v$ and $w$ disagree (by $1$) only in their $r$’th coordinate. Therefore $v^{\prime }$ and $w^{\prime }$ disagree by $1$ only in the $r$’th coordinate. Then there are two possibilities under case $(A)$.

1. $v^{\prime }$ and $w^{\prime }$ are successive points on some $D$-path of dimension $r$, or

2. $v^{\prime }$ and $w^{\prime }$ are successive points on the copy $L^r\ast m$ of $L^r$ or the copy $R^r\ast m$ of $R^r$ in $[m]$.

(resp. $R^r\ast m$) of $L^r$ (resp. $R^r$) in $[m]$.

Consider first possibility case $(A1)$, shown in Figure 12. Then we can take $v^{\prime },w^{\prime }\in D(u,r)$ with $head(D(u,r))=u$. So we must have $u\in [m1]\cup [mm]$, and by symmetry we can take $u\in [m1]$. So we have that $v^{\prime }$ and $w^{\prime }$ are in the same component of $[D(r+1)]$ as $u$, so $Source(w^{\prime })=Source(v^{\prime })\in [m1]$.

We claim that one of $v^{\prime },w^{\prime }$ is the head of its $D$-path in dimension $r+1$, while the other must be the tail of its $D$-path of this dimension, For this, note that $v^{\prime }$ and $w^{\prime }$ are neighbors in $P_m^{r+1}$ so are on opposite sides of the bipartition of $A_{r+1},B_{r+1}$ in step $5$ of the construction of $S_{r+1}$. So by step $6$ of that construction, $v^{\prime }$ and $w^{\prime }$ receive opposite head/tail designations for their $D$-paths dimension $r+1$, proving the claim.

So arbitrarily take $head(D(w^{\prime },r+1))=w^{\prime }$, forcing $tail(D(v^{\prime },r+1))=v^{\prime }$. Therefore $w$ is in the same tree component of $[D(r+1)]$ as $w^{\prime }$, so we get $Source(w)=Source(w^{\prime })=Source(v^{\prime })\in [m1]$ since $u\in [m1]$.

Now let $v^{″}=head(D(v^{\prime },r+1)$ and $w^{″}=tail(D(w^{\prime },r+1)$, so $v^{″},w^{″}\in [1]$. Then $v^{″}$ and $w^{″}$ are successive points on a path $D(u^{\prime },r)\subset [1]$, for some $u^{\prime }\in [1]$, corresponding to $D(u,r)\subset [m]$. (We note here that in possibility (2), $v^{″}$ and $w^{″}$ are successive points on either $L^r\ast 1$ or $R^r\ast 1$, which will be considered when $(2)$ is analyzed.) Since $D(u,r)$ and $D(u^{\prime },r)$, together with their heads and tails, are corresponding $D$-paths of dimension $r$ in $[m]$ and $[1]$ respectively, we have $D(u^{\prime },r)=D(u,r{)}^R$ by step $7$ of the construction of $S_{r+1}$. So the point $z\in D(u^{\prime },r)$ corresponding to $u$ is $tail(D(u^{\prime },r))$, noting also that $z\in [11]$. Hence $head(D(u^{\prime },r))\in [1m]$, and by renaming we can let $u^{\prime }=head(D(u^{\prime },r))\in [1m]$. So $Source(w^{″})=Source(v^{″})=Source(v)\in [1m]$ and still recall that $Source(w)\in [m1]$. The various $D$-paths and points are illustrated in Figure 12.

We now form the cycle $W^{\prime }$ in $S_{r+1}+vw$ as follows.

$$\begin{array}{rl}{W}^{\prime }=& w–v\stackrel{\text{L'b}}{\to }Source(v)\stackrel{P_L(Source(v))\text{ by Lc}}{\to }L(S_2(Source(v)))\stackrel{\text{La}}{\to }L([1m])\stackrel{L^r\ast 1}{\to }L([11])\stackrel{L^{r+1}}{\to }\\ & L([m1])\stackrel{\text{La}}{\to }L(S_2(Source(w)))\stackrel{P_L(Source(w))\text{ by Lc}}{\to }Source(w)\stackrel{\text{L'b}}{\to }w.\end{array}$$

We then take $R([mm])\notin W^{\prime }$, and form the three independent $R([mm])-W^{\prime }$ paths in $S_{r+1}+vw$ as follows.

$$\begin{array}{rl}{P}_1=& R([mm])\stackrel{R^r\ast m}{\to }R([m1])\stackrel{\text{La}}{\to }R(S_2(Source(w)))\stackrel{\text{Ld}}{\to }q(Source(w)),\\ & \text{(intersecting }{W}^{\prime }\text{ at }q(Source(w))\text{)},\\ P_2=& R([mm])\stackrel{\text{Lb}}{\to }L([mm])\stackrel{L^r\ast m}{\to }L([m1]),\text{(intersecting }{W}^{\prime }\text{ at }L([m1])\text{)},\\ P_3=& R([mm])\stackrel{R^{r+1}}{\to }R([1m])\stackrel{\text{La}}{\to }R(S_2(Source(v)))\stackrel{\text{Ld}}{\to }q(Source(v)),\\ & \text{(intersecting }{W}^{\prime }\text{ at }q(Source(v))\text{)}.\end{array}$$

Consider now possibility case $(A2)$, still in case $A$ and with $k=r$. Here $v^{\prime }$ and $w^{\prime }$ are successive points on $L^r\ast m$ or on $R^r\ast m$, say by symmetry on $R^r\ast m$. So $v^{″}$ and $w^{″}$ are corresponding successive points on $R^r\ast 1$. As before we can take $w^{\prime }=head(D(w^{\prime },r+1))$ and $v^{\prime }=tail(D(v^{\prime },r+1))$. This case is illustrated in Figure 13.

First we form the cycle $W^{″}$, indicated in bold in that figure, as follows.

$$W^{″}=w–v\stackrel{D(v^{″},r+1)}{\to }{v}^{″}\stackrel{R^r\ast 1}{\to }R([1m])\stackrel{R^{r+1}}{\to }R([mm])\stackrel{R^r\ast m}{\to }{w}^{\prime }\stackrel{D(w^{\prime },r+1)}{\to }w.$$

Now we take $L([11])\notin W^{″}$, and form three independent $L([11])–W^{″}$ paths as follows. $$\begin{array}{rl}{P}_1=& L([11])\stackrel{\text{Lb}}{\to }R([11])\stackrel{R^r\ast 1}{\to }{v}^{″},\text{(intersecting }{W}^{″}\text{ at }{v}^{″}\text{)},\\ P_2=& L([11])\stackrel{L^r\ast 1}{\to }L([1m])\stackrel{\text{Lb}}{\to }R([1m]),\text{(intersecting }{W}^{″}\text{ at }R([1m])\text{)},\\ P_3=& L([11])\stackrel{L^{r+1}}{\to }L([m1])\stackrel{\text{Lb}}{\to }R([m1])\stackrel{R^r\ast m}{\to }{w}^{\prime },\text{(intersecting }{W}^{″}\text{ at }{w}^{″}\text{)}.\end{array}$$

Still assuming $k=r$, consider case $(B)$; that is, where one of $v,w$ is in $L^{r+1}\cup R^{r+1}$ while the other is in $[D^{\prime }(r+1)]$ and illustrated in Figure 14. By symmetry we can suppose $v\in L^{r+1}$, the latter having endpoints $L([11])$ and $L([m1])$, the case $v\in R^{r+1}$ being essentially the same. Now $w\in D(w^{\prime },r+1)$ where $w^{\prime }\in [m]\cup [1]$, and by symmetry we take $w^{\prime }\in [m]$.

We can further specify $w^{\prime }$ as follows. Now $k=r$ implies $w_{r+1}=v_{r+1}$ and $|w_r–v_r|=1$. Since $v_r=L([m1]{)}_r$ and $w_r^{\prime }=w_r$, we then obtain $|w_r^{\prime }–L([m1]{)}_r|=1$. So this forces $w^{\prime }$ to be the point on $L^r\ast m$ adjacent to $L([m1])$.

Since $L([11])\in A_{r+1}$, then $L([m1])\in B_{r+1}$ because $m$ is even. Hence $w^{\prime }\in A_{r+1}$, so by construction $w^{\prime }=head(D(w^{\prime },r+1))$. Then in $S_{r+1}+vw$ we have have a cycle $Y$, the point $R([mm])\notin Y$, and three independent $R([mm])–Y$ paths $P_i$, $1\le i\le 3$, as follows. In Figure 14, $Y$ is the $4$-cycle illustrated in bold lines, and the paths $P_i$ in dashed lines. $$\begin{array}{rl}Y=& w–v\stackrel{L^{r+1}}{\to }L([m1])\stackrel{L^r\ast m}{\to }{w}^{\prime }\stackrel{D(w^{\prime },r+1)}{\to }w,\\ P_1=& R([mm])\stackrel{R^r\ast m}{\to }R([m1])\stackrel{\text{Lb}}{\to }L([m1]),\text{(intersecting }Y\text{ at }L([m1])\text{)},\\ P_2=& R([mm])\stackrel{\text{Lb}}{\to }L([mm])\stackrel{L^r\ast m}{\to }{w}^{\prime },\text{(intersecting }Y\text{ at }{w}^{\prime }\text{)},\\ P_3=& R([mm])\stackrel{R^{r+1}}{\to }R([1m])\stackrel{\text{Lb}}{\to }L(1m)\stackrel{L^r\ast 1}{\to }L([11])\stackrel{L^{r+1}}{\to }v,\text{(intersecting }Y\text{ at }v\text{)}.\end{array}$$

This completes the analysis of the possibility $k=r$, and we now move to the assumption $k<r$. Again we begin with case $(A)$, where $v,w\in [D^{\prime }(r+1)]$. Figure 15 illustrates this case. The labeled vertices in this figure are explained in the discussion which follows, and the reader may wish to follow this discussion using the figure for illustration.

Let $v^{\prime },w^{\prime }\in [1]$ correspond to $v$ and $w$ in $[1]$; that is, $v_{r+1}^{\prime }=w_{r+1}^{\prime }=1$ while $v_j^{\prime }=v_j$ and $w_j^{\prime }=w_j$ for $1\le j\le r$. Similarly let $v^{″},w^{″}\in [m]$ be such that $v_{r+1}^{″}=w_{r+1}^{″}=m$ while $v_j^{″}=v_j$ and $w_j^{″}=w_j$ for $1\le j\le r$. Since $v_r^{″}=v_r=w_r=w_r^{″}$, we see that $v^{″}$ and $w^{″}$ are on distinct $D$-paths of dimension $r$ in $[m]$, while $v^{\prime }$ and $w^{\prime }$ are on the corresponding distinct $D$-paths of dimension $r$ in $[1]$. Now $v^{\prime }$ and $w^{\prime }$ are neighbors in $P_m^{r+1}$, so are on opposite sides of the bipartition $A_{r+1},B_{r+1}$ of $P_m^{r+1}$. So $v^{\prime }$ and $w^{\prime }$ receive opposite head/tail designations in $D(v^{\prime },r+1)$ and $D(w^{\prime },r+1)$ respectively. By symmetry we can take $v^{\prime }=head(D(v^{\prime },r+1))$ so $w^{\prime }=tail(D(w^{\prime },r+1))$, so $v^{\prime }\in A_{r+1}$ and $w^{\prime }\in B_{r+1}$. Therefore $v^{″}=tail(D(v^{\prime },r+1))$ and $w^{″}=head(D(w^{\prime },r+1))$ and $v^{″}$ and $w^{″}$ are neighbors in $P_m^{r+1}$ with $v^{″}\in B_{r+1}$ and $w^{″}\in A_{r+1}$.

Now let $w_D^{″}\in [m1]$ be the vertex with $(w_D^{″}{)}_r=1$ and $(w_D^{″}{)}_j=w_j^{″}$ for $j\ne r$. Similarly let $v_D^{″}\in [m1]$ (resp. $v_D^{\prime }\in [11]$) be such that $(v_D^{″}{)}_r=1$ and $(v_D^{″}{)}_j=v_j^{″}$ for $j\ne r$ (resp. $(v_D^{\prime }{)}_r=1$ and $(v_D^{″}{)}_j=v_j^{\prime }$ for $j\ne r$). So we have $w^{″}\in D(w_D^{″},r)$, and by symmetry we can take $w_D^{″}=head(D(w_D^{″},r))$. So we have $Source(w)=Source(w^{″})\in [m1]$. Again, the situation is illustrated in Figure 15.

We claim that $Source(v)\in [11]$. For this it suffices to show that $Source(v^{\prime })\in [11]$ since $v$ and $v^{\prime }$ are joined by a path (in fact he subpath subpath $v\cdots v^{\prime }$ of $D(v^{″},r)$) in $D(r+1)$. Since $v_r^{″}=w_r^{″}$ we have $dis{t}_{S_{r+1}}(v^{″},v_D^{″})=dis{t}_{S_{r+1}}(w^{″},w_D^{″})$. So since $v^{″}$ and $w^{″}$ are on opposite sides of the bipartition $(A_{r+1},B_{r+1})$, it follows that $v_D^{″}$ and $w_D^{″}$ are also on opposite sides of the same bipartition. So we get $v_D^{″}=tail(D(v_D^{″},r))$ since $w_D^{″}=head(D(w_D^{″},r))$. But since $D(v_D^{″},r)=D(v_D^{\prime },r{)}^R$ by construction, we get $v_D^{\prime }=head(D(v_D^{\prime },r))$. It follows that $Source(v^{\prime })=Source(v_D^{\prime })\in [11]$, so finally $Source(v)\in [11]$. Again see Figure 15.

We can then form our cycle $C$ (shown in bold in Figure 15 ) and point $R([mm])\notin C$, together with three independent $R[mm]–C$ paths (shown dashed in that figure) as follows. $$\begin{array}{rl}C=& w–v\stackrel{D(v^{\prime },r+1)}{\to }{v}^{\prime }\stackrel{\text{path through }{v}_D^{\prime }}{\to }Source(v)\stackrel{P_L(Source(v))}{\to }L(S_2(Source(v)))\stackrel{\text{La}}{\to }\\ & L([11])\stackrel{L^{r+1}}{\to }L([m1])\stackrel{\text{La}}{\to }L(S_2(Source(w)))\stackrel{P_L(Source(w))}{\to }\\ & Source(w)\stackrel{\text{path through }{w}_D^{″},w^{″}}{\to }w,\\ P_1=& R([mm])\stackrel{R^r\ast m}{\to }R([m1])\stackrel{\text{La}}{\to }R(S_2(Source(w)))\stackrel{\text{Ld}}{\to }q(Source(w)),\\ & \text{(intersecting }C\text{ at }q(Source(w))\text{)},\\ P_2=& R([mm])\stackrel{\text{Lb}}{\to }L([mm])\stackrel{L^r\ast m}{\to }L([m1]),\text{(intersecting }C\text{ at }L([m1])\text{)},\\ P_3=& R([mm])\stackrel{R^{r+1}}{\to }R([1m])\stackrel{\text{Lb}}{\to }L([1m])\stackrel{L^r\ast 1}{\to }L([11]),\text{(intersecting }C\text{ at }L([11])\text{)}.\end{array}$$

Still with $k<r$, we finally consider case $(B)$, where one of $\{v,w\}$ is in $L^{r+1}\cup R^{r+1}$ while the other is in $[D^{\prime }(r+1)]$. One of the subcases here described later is illustrated in Figure 16. That figure is still useful for the reductions which follow.

By symmetry we can take $v\in L^{r+1}$, recalling that the path $L^{r+1}$ has ends $L([m1])$ and $L([11])$. Also $w=D(w^{\prime },r+1)$ where we can take $w^{\prime }\in [m]$ or $w^{\prime }\in [1]$, and we can arbitrarily take $w^{\prime }\in [m]$. With the same argument as in the case $k=r$, we find that $w^{\prime }$ must be a neighbor in $P_m^{r+1}$ of $L([m1])$ across an edge of dimension $k$. A straightforward induction on $r$ shows that $de{g}_{P_m^{r+1}}(x)=de{g}_{S_{r+1}}(x)=r+1$ for $x\in \{L([11]),L([1m]),L([m1]),L([mm])\}$. Hence $w^{\prime }$ is a neighbor of $L([m1])$ in $S_{r+1}$. Observe further that every neighbor of $L([m1])$ in $S_{r+1}$ across an edge of dimension $k\ge 3$ lies on some left attachment path $L^k\ast B$ for some length $r+1-k$ string $B$ over $\{m,1\}$, while for dimension $k=1,2$ the two neighbors of $L([m1])$ are in the square $S_2(L([m1]))$ containing $L([m1])$.

We are therefore reduced to the following two cases defined by $w^{\prime }$:

1. $w^{\prime }$ is the point adjacent to $L([m1])$ on some attachment path $L^k\ast B$, or

2. $w^{\prime }$ belongs to no attachment path, in which case $w^{\prime }$ is one of the two neighbors of $L([m1])$ in $S_2(L([m1]))$.

Consider first case a), illustrated in Figure 16 with details which follow. Then $L^k\ast B$ is in a subgraph $S=S_k\ast B\subset [m1]$. In Figure 16 we illustrate the subgraphs $S(1)$ and $S(m)$ by two smaller rectangles inside the lower left larger rectangle representing $[m1]$. The ends of the attachment path $L^k\ast B$ are shown as $L([m1])$ and $F$, while the ends of $R^k\ast B$ as $G$ and $R(S)=H$. (Though we don’t use this in the construction which follows, we can deduce $B$ by observing that every vertex in $S$ has the same $r+1-k$ length suffix $B$ as $L([m1])$, so $B=1^{r-k}m$. From this and $L([m1])=1^{r}m$ we can deduce the coordinates $F=1^{k-1}m{1}^{r-k}m$, $G=m^{k-1}1\ast 1^{r-k}m$ and $R(S)=m^k\ast 1^{r-k}m$.)

We now have in $S_{r+1}+vw$ the cycle $C^{\prime }$, the point $R(S)\notin C^{\prime }$, and three independent $R(S)–C^{\prime }$ paths $R_i$ as follows and illustrated in the Figure 16.

$$\begin{array}{rl}{C}^{\prime }=& w–v\stackrel{L^{r+1}}{\to }L([m1])\stackrel{L^k\ast B}{\to }{w}^{\prime }\stackrel{D(w^{\prime },r+1)}{\to }w,\\ R_1=& R(S)\stackrel{Lb}{\to }F\stackrel{L^k\ast B}{\to }{w}^{\prime },\text{(intersecting }{C}^{\prime }\text{ at }{w}^{\prime }\text{)},\\ R_2=& R(S)\stackrel{R^k\ast B}{\to }G\stackrel{Lb}{\to }L([m1]),\text{(intersecting }{C}^{\prime }\text{ at }L([m1])\text{),}\\ R_3=& R(S)\stackrel{La}{\to }R([m1])\stackrel{R^r\ast m}{\to }R([mm])\stackrel{R^{r+1}}{\to }R([1m])\stackrel{Lb}{\to }L([1m])\stackrel{L^r\ast 1}{\to }L([11])\stackrel{L^{r+1}}{\to }v,\\ & \text{(intersecting }{C}^{\prime }\text{ at }v\text{).}\end{array}$$

Now consider the second case b); that is, where $w^{\prime }$ belongs to no attachment path and is adjacent to $L([m1])$ in $S_2(L([m1]))$. Observe here that $w^{\prime }=head(D(w^{\prime },r+1))$. This is because $L([11])=1^{r+1}\in A_{r+1}$, so $L([m1])\in B_{r+1}$ (since $m$ is even), so $w^{\prime }\in A_{r+1}\cap [m]$ since $w^{\prime }$ is a neighbor of $L([m1])$. Now in $S_{r+1}+vw$ we form a cycle $C^{″}$, the point $R([mm])\notin C^{″}$, and three independent $R([mm])–C^{″}$ paths $Q_i$ as follows. $$\begin{array}{rl}{C}^{″}=& w–v\stackrel{L^{r+1}}{\to }L([m1])\stackrel{\text{edgein }{S}_2(L([m1]))}{\to }{w}^{\prime }\stackrel{D(w^{\prime },r+1)}{\to }w,\\ Q_1=& R([mm])\stackrel{\text{Lb}}{\to }L([mm])\stackrel{L^r\ast m}{\to }L([m1]),\text{(intersecting }{C}^{″}\text{ at }L([m1])\text{)},\\ Q_2=& R([mm])\stackrel{R^r\ast m}{\to }R([m1])\stackrel{\text{Lb}}{\to }R(S_2(w^{\prime }))\stackrel{\text{pathin }{S}_2(w^{\prime })}{\to }{w}^{\prime },\text{(intersecting }{C}^{″}\text{ at }{w}^{\prime }\text{)},\\ Q_3=& R([mm])\stackrel{R^{r+1}}{\to }R([1m])\stackrel{\text{Lb}}{\to }L([1m])\stackrel{L^r\ast 1}{\to }L([11])\stackrel{L^{r+1}}{\to }v,\text{(intersecting }{C}^{″}\text{ at }v\text{)}.\end{array}$$