ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P2.09 / 317–326
https://doi.org/10.26493/1855-3974.2577.25d
(Also available at http://amc-journal.eu)
Linkedness of Cartesian products of complete
graphs*
Leif K. Jørgensen
Department of Mathematical Sciences, Aalborg University, Denmark
Guillermo Pineda-Villavicencio † , Julien Ugon ‡
Federation University, Ballarat, Australia and
School of Information Technology, Deakin University, Geelong, Australia
Received 9 March 2021, accepted 26 August 2021, published online 27 May 2022
Abstract
This paper is concerned with the linkedness of Cartesian products of complete graphs.
A graph with at least 2k vertices is k-linked if, for every set of 2k distinct vertices organised
in arbitrary k pairs of vertices, there are k vertex-disjoint paths joining the vertices in the
pairs.
We show that the Cartesian product Kd1+1 × Kd2+1 of complete graphs Kd1+1 and
Kd2+1 is ⌊(d1 + d2)/2⌋-linked for d1, d2 ≥ 2, and this is best possible.
This result is connected to graphs of simple polytopes. The Cartesian product
Kd1+1 ×Kd2+1 is the graph of the Cartesian product T (d1)× T (d2) of a d1-dimensional
simplex T (d1) and a d2-dimensional simplex T (d2). And the polytope T (d1) × T (d2) is
a simple polytope, a (d1 + d2)-dimensional polytope in which every vertex is incident to
exactly d1 + d2 edges.
While not every d-polytope is ⌊d/2⌋-linked, it may be conjectured that every simple d-
polytope is. Our result implies the veracity of the revised conjecture for Cartesian products
of two simplices.
Keywords: k-linked, cyclic polytope, connectivity, dual polytope, linkedness, Cartesian product.
Math. Subj. Class. (2020): 05C40, 52B05
*The authors want to thank the referee for his/her comments, which have certainly helped to improve the
presentation of the paper.
†Corresponding author. Guillermo would like to thank the hospitality of Leif Jørgensen, and the Department
of Mathematical Sciences at Aalborg University, where this research started.
‡Julien Ugon’s research was supported by the ARC discovery project DP180100602.
E-mail addresses: leifkjorgensen@gmail.com (Leif K. Jørgensen), work@guillermo.com.au (Guillermo
Pineda-Villavicencio), julien.ugon@deakin.edu.au (Julien Ugon)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
318 Ars Math. Contemp. 22 (2022) #P2.09 / 317–326
1 Introduction
Denote by V (X) the vertex set of a graph. Given sets A,B of vertices in a graph, a path
from A to B, called an A−B path, is a (vertex-edge) path L := u0 . . . un in the graph such
that V (L) ∩ A = {u0} and V (L) ∩ B = {un}. We write a − B path instead of {a} − B
path, and likewise, write A− b path instead of A− {b}.
Let G be a graph and X a subset of 2k distinct vertices of G. The elements of X
are called terminals. Let Y := {{s1, t1}, . . . , {sk, tk}} be an arbitrary labelling and (un-
ordered) pairing of all the vertices in X . We say that Y is linked in G if we can find disjoint
si − ti paths for i ∈ [1, k], the interval 1, . . . , k. The set X is linked in G if every such
pairing of its vertices is linked in G. Throughout this paper, by a set of disjoint paths, we
mean a set of vertex-disjoint paths. If G has at least 2k vertices and every set of exactly 2k
vertices is linked in G, we say that G is k-linked.
This paper studies the linkedness of Cartesian products of complete graphs. Linkedness
of Cartesian products has been studied in the past [4]. The Cartesian product G1 ×G2 of
two graphs G1 and G2 is the graph defined on the pairs (v1, v2) with vi ∈ Gi and with
two pairs (u1, u2) and (v1, v2) being adjacent if, for some ℓ ∈ {1, 2}, uℓvℓ ∈ E(Gℓ) and
ui = vi for i ̸= ℓ. We prove that the Cartesian product Kd1+1×Kd2+1 of complete graphs
Kd1+1 and Kd2+1 is ⌊(d1 + d2)/2⌋-linked for d1, d2 ≥ 0, and that there are products that
are not ⌊(d1 + d2 + 1)/2⌋-linked; hence this result is best possible. Here Kt denotes the
complete graph on t vertices.
Our result is connected to questions on the linkedness of a polytope. A (convex) poly-
tope is the convex hull of a finite set X of points in Rd; the convex hull of X is the smallest
convex set containing X . The dimension of a polytope in Rd is one less than the maximum
number of affinely independent points in the polytope; a set of points p⃗1, . . . , p⃗k in Rd is
affinely independent if the k − 1 vectors p⃗1 − p⃗k, . . . , p⃗k−1 − p⃗k are linearly independent.
A polytope of dimension d is referred to as a d-polytope.
The Cartesian product P × P ′ of a d-polytope P ⊂ Rd and a d′-polytope P ′ ⊂ Rd′ is
the Cartesian product of the sets P and P ′:
P × P ′ =
{(
p
p′
)
∈ Rd+d
′
∣∣∣∣ p ∈ P, p′ ∈ P} .
The resulting polytope is (d + d′)-dimensional. The graph G(P ) of a polytope P is the
undirected graph formed by the vertices and edges of the polytope. It follows that the graph
G(P ×P ′) of the Cartesian product P ×P ′ is the Cartesian product G(P )×G(P ′) of the
graphs G(P ) and G(P ′).
A d-simplex T (d) is the convex hull of d + 1 affinely independent points in Rd. The
graph of T (d) is the complete graph Kd+1. As a consequence, our result implies that the
graph of the Cartesian product T (d1) × T (d2) is ⌊(d1 + d2)/2⌋-linked for d1, d2 ≥ 0.
Henceforth, if the graph of a polytope is k-linked we say that the polytope is also k-linked.
The first edition of the Handbook of Discrete and Computational Geometry [3, Prob-
lem 17.2.6] posed the question of whether or not every d-polytope is ⌊d/2⌋-linked. This
question was answered in the negative by [2]. None of the known counterexamples are sim-
ple d-polytopes, d-polytopes in which every vertex is incident to exactly d edges. Hence, it
may be hypothesised that the conjecture holds for such polytopes.
Conjecture 1.1. Every simple d-polytope is ⌊d/2⌋-linked for d ≥ 2.
L. K. Jørgensen et al.: Linkedness of Cartesian products of complete graphs 319
Cartesian products of simplices are simple polytopes, and so our result supports this
revised conjecture. Furthermore, Cartesian products of simplices and duals of cyclic poly-
topes are related; the dual of a cyclic d-polytope with d+2 vertices is the Cartesian product
of a ⌊d/2⌋-simplex and a ⌈d/2⌉-simplex [6, Example 0.6]. Hence we obtain that the dual
of a cyclic d-polytope on d+ 2 vertices is also ⌊d/2⌋-linked for d ≥ 2.
Unless otherwise stated, the graph theoretical notation and terminology follows from
[1] and the polytope theoretical notation and terminology from [6]. Moreover, when refer-
ring to graph-theoretical properties of a polytope such as linkedness and connectivity, we
mean properties of its graph.
2 Linkedness of Cartesian products of complex graphs
The contribution of this section is a sharp theorem (Theorem 2.1) that tells the story of the
linkedness of Cartesian product of two complete graphs.
(e)
s1
t2
s2
t1
s3 t3 sk tk· · ·
· · ·
(a)
s1
s2
s3t2
t3
t1
s1
s2
s3
t2
t3
t1
s4
t4
s1
s2
s3
t5
s5
s6
s4
t4
t6
t1t2
t3
(b)
(c)
s1
s2
s3t5
s5
t1
s4
t3
(d)
t4
t2
Figure 1: No feasible linkage problems for Kd1+1 × Kd2+1, k = ⌊(d1 + d2 + 1)/2⌋,
d1 ≤ 2 and d2 > d1. (a) The case d1 = 1 and even d2 with d2 > d1. (b) The case d1 = 2
and d2 = 3. (c) The case d1 = 2 and d2 = 5. (d) The case d1 = 2 and d2 = 7. (e) The
case d1 = 2 and d2 = 9. Each row of each part (a)-(e) is a complete graph whose edges
have not been drawn.
Theorem 2.1. The Cartesian product of two complete graphs Kd1+1 and Kd2+1 is
⌊(d1 + d2)/2⌋-linked for every d1, d2 ≥ 0.
Remark 2.2. Theorem 2.1 is best possible. There are products Kd1+1 × Kd2+1 that are
not ⌊(d1 + d2 + 1)/2⌋-linked:
1. K2 ×Kd2+1 for even d2 ≥ 1, and
320 Ars Math. Contemp. 22 (2022) #P2.09 / 317–326
2. K3 ×Kd2+1 for d2 = 1, 3, 5, 7, 9.
For each of these cases, Figure 1 provides a pairing of terminals that cannot be
⌊(d1 + d2 + 1)/2⌋-linked. We conjecture these are the only such cases.
An immediate corollary of Theorem 2.1 is the following.
Corollary 2.3. The Cartesian product of two simplices T (d1) and T (d2) is ⌊(d1+d2)/2⌋-
linked for every d1, d2 ≥ 0.
The notions of linkage, linkage problem, and valid path will simplify our arguments.
A linkage in a graph is a subgraph in which every component is a path. Let X be a set of
vertices in a graph and let Y := {{s1, t1} , . . . , {sk, tk}} be a pairing of all the vertices of
X . A Y -linkage {L1, . . . , Lk} is a set of disjoint paths with the path Li joining the pair
{si, ti} for i = 1, . . . , k. We may also say that Y represents our linkage problem, and if Y
is linked in G then our linkage problem is feasible and infeasible otherwise. A path in the
graph is called X-valid if no inner vertex of the path is in X . Let X be a set of vertices
in a graph G. Denote by G[X] the subgraph of G induced by X , the subgraph of G that
contains all the edges of G with vertices in X . Write G−X for G[V (G) \X].
Consider a linkage problem Y := {{s1, t1}, . . . , {sk, tk}} on a set X of 2k vertices
in a graph G. Consider a linkage L from a subset Z of X to some set Z ′ disjoint from
X and label the vertices of Z ′ such that the path in L with end zi ∈ Z has its other end
z′i ∈ Z ′. Then the linkage L in G induces a linkage problem Y ′ in (G−V (L))∪Z ′ where
the vertices of X \ Z remain and the vertices of Z have been replaced by the vertices of
Z ′. Slightly abusing terminology, we also call terminals the vertices of Z ′. If the problem
Y ′ is feasible in (G− V (L)) ∪ Z ′, so is the problem Y in G.
Since we make heavy use of Menger’s theorem [1, Theorem. 3.3.1], we next remind
the reader of one of its consequences.
Theorem 2.4 (Menger’s theorem). Let G be a k-connected graph, and let A and B be two
subsets of its vertices, each of cardinality at least k. Then there are k disjoint A−B paths
in G.
We fix some notation and terminology for the remaining of the section. Let G denote
the graph Kd1+1 ×Kd2+1. We think of G = Kd1+1 ×Kd2+1 as a grid with d1 + 1 rows
and d2 + 1 columns. In this way, the entry in Row i and Column j can be referred to as
G[i, j].
When we write about a row r of subgraph G′ of G, we think of r as a subgraph of G′
and as the number r so that we can write about the rth row of G′ or G; this ambiguity
should cause no confusion. An entry in the grid Kd1+1 ×Kd2+1 with no terminal is said
to be free, as is a row or a column of a subgraph of G with no terminal. A row or a column
of a subgraph of G with every entry being occupied by a terminal is said to be full.
We need the following induced subgraphs of G:
Cab...z, the subgraph formed by the union of Columns a, b, . . . , z;
C̄ab...z, the subgraph obtained by removing Columns a, b, . . . , z;
Rab...z, the subgraph formed by the union of Rows a, b, . . . , z;
R̄ab...z, the subgraph obtained by removing Rows a, b, . . . , z;
Aα, the induced subgraph of C̄12 obtained by removing its first α rows; and
Bα, the subgraph of C12 obtained by removing its first α rows.
L. K. Jørgensen et al.: Linkedness of Cartesian products of complete graphs 321
For instance, C̄1 denotes the subgraph of G obtained by removing the first column, C12
the subgraph formed by the first two columns of G, and C̄12 denotes the subgraph obtained
by removing the first two columns of G; observe C̄12 is isomorphic to Kd1+1 × Kd2−1.
Figure 2 depicts some of the aforementioned subgraphs of Kd1+1 ×Kd2+1.
...
...
...
...
...
...
...
...
...
...
AαBα
 α rows d1 + 1 – α rows︸ ︷︷ ︸
C12
︸ ︷︷ ︸
C̄12
Figure 2: Depiction of the subgraphs Bα, Aα, C12, and C̄12 of Kd1+1 ×Kd2+1.
The connectivity of Kd1+1 ×Kd2+1 is stated below.
Lemma 2.5 (Špacapan [5, Theorem 1]). The (vertex)connectivity of Kd1+1 × Kd2+1 is
precisely d1 + d2.
We continue fixing further notation. Henceforth let k := ⌊(d1 + d2)/2⌋. And let X be
a subset of 2k vertices of G and let Y := {{s1, t1}, . . . , {sk, tk}} be a pairing of all the
vertices in X .
We first settle the simple cases of (0, d2) and (1, d2) for d2 ≥ 0.
Proposition 2.6 (Base cases). For d2 ≥ 0 the Cartesian products K1 × Kd2+1 and
K2 ×Kd2+1 are both ⌊(1 + d2)/2⌋-linked. This statement is best possible.
Proof. The lemma is true for the pair (0, d2) for each d2 ≥ 0, since K1×Kd2+1 = Kd2+1
and Kd2+1 is ⌊(1 + d2)/2⌋-linked. This is best possible.
The graph K2 × Kd2+1 is (1 + d2)-connected by Lemma 2.5. Use Menger’s theo-
rem (Theorem 2.4) to bring the 1 + d2 terminals to the subgraph R̄1 through a linkage
{S1, . . . , Sk, T1, . . . , Tk} with Si := si − R̄1 and Ti := ti − R̄1 for i ∈ [1, k]. Letting
{s̄i} := V (Si) ∩ V (R̄1) and {t̄i} := V (Ti) ∩ V (R̄1), we produce a new linkage prob-
lem Y ′ := {{s̄1, t̄1}, . . . , {s̄k, t̄k}} in R̄1 whose feasibility implies that of Y in G. To
solve Y ′ link the pairs of Y ′ in the subgraph R̄1, which is isomorphic to Kd2+1, using
the ⌊(1 + d2)/2⌋-linkedness of Kd2+1. For even even d2, Figure 1(a) shows an infeasible
linkage problem with ⌊(2 + d2)/2⌋ pairs in the graph K2 ×Kd2+1.
In what follows we aim to find a Y -linkage {L1, . . . , Lk} in G with Li joining the pair
{si, ti} of Y for i ∈ [1, k]. Our proof is by induction on (d1, d2) with the base cases settled
in Proposition 2.6. If there is a pair of Y , say {s1, t1}, lying in some column or row of
G, say in Column 1, we send every terminal si ∈ C1 that is different from s1 and t1 and
that is not adjacent to ti to the subgraph C̄1, and apply the induction hypothesis on C̄1.
Otherwise, we may assume every pair of Y lies in two distinct columns or rows, say the
pair {s1, t1} lies in C12; then we send every terminal si ∈ C12 that is different from s1 and
322 Ars Math. Contemp. 22 (2022) #P2.09 / 317–326
t1 and that is not adjacent to ti to the subgraph C̄12, and apply the induction hypothesis to
C̄12. We develop these ideas below.
The definition of k-linkedness gives the following lemma at once; we will use it im-
plicitly hereafter.
Lemma 2.7. Let ℓ ≤ k. Let X be a set of 2ℓ distinct vertices of a k-linked graph K, let Y
be a labelling and pairing of the vertices in X , and let Z be a set of 2k − 2ℓ vertices in K
such that X ∩ Z = ∅. Then there exists a Y -linkage in K that avoids every vertex in Z.
Besides, basic algebraic manipulation yields the following inequality.
Lemma 2.8. If x ≥ 2 and y ≥ 2 then x(y − 1) > x+ y − 3.
Proof. The inequality simplifies to (x− 1)(y − 2) > −1.
We are now ready to put together all the elements of the proof of Theorem 2.1.
Proof of Theorem 2.1. Let k := ⌊(d1 + d2)/2⌋. Then d1 + d2 ≥ 2k.
Proposition 2.6 gives the result for the pairs (d1, 0), (0, d2), (d1, 1), and (1, d2) for each
d1, d2 ≥ 0. Hence, our bidimensional induction on (d1, d2) can start with the assumption
of d1, d2 ≥ 2.
We first deal with the case where a pair in Y , say {s1, t1}, lies in some column or some
row of G, say in Column 1.
Case 1. A pair in Y , say {s1, t1}, lies in Column 1.
The induction hypothesis ensures that the subgraph C̄1 is (k − 1)-linked. Hence it
suffices to show that all the terminals in C1 other than s1, t1 can be moved to C̄1 via a
linkage; Menger’s theorem (Theorem 2.4) guarantees this.
Let U be the set of terminals in C1 other than s1 and t1, and let W be the set of terminals
in C̄1. Then |U |+|W | ≤ d1+d2−2, as |U |+|W | = 2k−2 and 2k ≤ d1+d2. Besides, the
subgraph G− (W ∪{s1, t1}) is |U |-connected, as G is (d1 + d2)-connected (Lemma 2.5).
In the case of d1, d2 ≥ 2, Lemma 2.8 yields that C̄1 has more than |U ∪W | vertices:
|C̄1| = (d1 + 1)d2 > d1 + 1 + d2 + 1− 3 > d1 + d2 − 2 = |U |+ |W |.
Use Menger’s theorem (Theorem 2.4) to bring the |U | terminals in C1 to the subgraph
C̄1 through a linkage YU . For every path L in YU , if si ∈ L, let {s̄i} := V (L) ∩ V (C̄1)
and if ti ∈ L let {t̄i} := V (L)∩V (C̄1). For si ∈ W (respectively ti ∈ W ) let s̄i = si (re-
spectively t̄i = ti). This produces a new linkage problem Y ′ := {{s̄2, t̄2}, . . . , {s̄k, t̄k}}
in C̄1 whose feasibility implies that of Y in G, since s1 and t1 are adjacent in C1. The
(k − 1)-linkedness of C̄1 now settles the case.
By symmetry, we can assume that every pair {si, ti} in Y lies in two different columns
or rows and that si, ti are not adjacent. Without loss of generality, assume that
s1 is in Column 1 and t1 is in Column 2 of C12. (∗)
The induction hypothesis also ensures that both C̄12 and R̄12 are (k − 1)-linked. We
consider two further cases based on the number of terminals in C12 or R12.
Case 2. The subgraph C12 contains precisely d1 + 2 − α terminals, including {s1, t1},
where 0 ≤ α ≤ d1.
L. K. Jørgensen et al.: Linkedness of Cartesian products of complete graphs 323
Excluding {s1, t1}, there are at most d1 terminals in C12, and there are d1+1 internally-
disjoint s1 − t1 paths in C12 of length at most three: two length-two paths and d1 − 1
length-three paths. One of these s1 − t1 paths, say L1, avoids every other terminal in C12.
Without loss of generality, assume that Row 1 in C12 is part of the path L1; that is,
{G[1, 1], G[1, 2]} ⊆ V (L1). (∗∗)
In the subcase α = d1, every pair in Y \{s1, t1} is in C̄12, and the induction hypothesis
on C̄12 settles the subcase.
Suppose that α = d1 − 1, say C12 contains {s1, t1, s2}. Then s2 ∈ B1 and t2 ∈ C̄12.
We may assume s1, s2 are in Column 1 and t1 is in Column 2. We show there is an X-valid
s2 −A1 path L′2 such that the vertex s̄2 ∈ V (L′2) ∩ V (A1) is either t2 or a nonterminal.
Through each entry of Column 1 of B1, there are d2 − 1 paths form s2 to A1 of length
at most two (one for each column in A1). Moreover, there are at least d1 − 1 free entries
in Column 1 of B1. Therefore, to ensure the existence of L′2, we need to show that at least
one of these (d1 − 1)(d2 − 1) paths from s2 to A1 either contains t2 or a nonterminal in
A1. Indeed, according to Lemma 2.8, the inequality
(d1 − 1)(d2 − 1) > d1 − 1 + d2 − 3 ≥ |X \ {s1, t1, s2, t2}|
holds for d1, d2 ≥ 2. Hence we get the existence of L′2. As a result, the solution of the new
problem Y ′ := {{s̄2, t2} , {s3, t3} , . . . , {sk, tk}} in C̄12 induces a solution of the problem
Y in G. And the solution of Y ′ follows from the (k − 1)-linkedness of C̄12.
Henceforth assume that α ≤ d1 − 2. To finalise Case 2, we require a couple of claims.
Claim 2.9. Suppose that there are at most d1 +2−α terminals in Bα+1 = Kd1−α ×K2.
Then there is an injection from the set of rows of Bα+1 that contain two terminals x1, x2
such that {x1, x2}∩ {s1, t1} = ∅ to the set of rows of Bα+1 that contain no terminal other
than possibly s1 and t1.
Proof. This follows from a simple counting argument. The number of rows in Bα+1 is
d1 − α. Let m denote the number of rows of Bα+1 that contain two terminals x1, x2 such
that {x1, x2}∩{s1, t1} = ∅ and let n := |(X ∩V (Bα+1)) \ {s1, t1} |; that is, n counts the
total number of terminals in Bα+1 other than s1 and t1. It follows that the number of rows
of Bα+1 that contain precisely one terminal x ̸∈ {s1, t1} is n− 2m; either s1 or t1 may be
in these rows. As a result, the number of rows of Bα+1 that contain no terminal other than
{s1, t1} is d1 − α −m − (n − 2m). Combining n ≤ d1 − α with all these numbers, we
get that
d1 − α−m− (n− 2m) = d1 − α− n+m ≥ d1 − α− (d1 − α) +m = m.
The claim is proved.
Claim 2.10. Suppose that there are at most d1+2−α terminals in Bα+1 = Kd1−α×K2.
If every row in the subgraph Aα+1 = Kd1−α ×Kd2−1 of C̄12 has a free entry, then, for
every terminal x ̸∈ {s1, t1} in Bα+1, there is an X-valid x− Aα+1 path L to a free entry
in Aα+1; and all these X-valid paths are disjoint.
Proof. If a row of Bα+1 contains exactly one terminal x ̸∈ {s1, t1}, then send x to a
free entry in the same row of Aα+1. Let x1 and x2 be two terminals in Bα+1 that satisfy
324 Ars Math. Contemp. 22 (2022) #P2.09 / 317–326
{x1, x2}∩{s1, t1} = ∅ and occupy a row rf of Bα+1. From Claim 2.9 ensues the existence
of a row re of Bα+1 that contain no terminal other than possibly s1 and t1; in short, there
is at least a free entry in re.
Consider a pair (rf , re) of rows granted by Claim 2.9. Send either x1 or x2, say x1,
to the free entry in the row re of Aα+1 passing through the corresponding free entry in the
row re of Bα+1, and send x2 to a free entry in the row rf of Aα+1. The proof of the claim
is now complete.
Now suppose that α = 0 or 2 ≤ α ≤ d1 − 2. In this subcase, the subgraph C̄12
contains at most α full rows: if α + 1 rows were full in C̄12 then there would be at least
(α+1)(d2−1) terminals in C̄12 but (α+1)(d2−1) > d2−2+α (Lemma 2.8). Even when
the path L1 uses the first row of C12 by (∗∗), there is no loss of generality by assuming that
the full rows of C̄12 are among the first α + 1 rows of C̄12. It follows that every row of
Aα+1 has a free entry.
Aα+1
 α + 1 rows d1 – α rows︸ ︷︷ ︸
C12
s2
t2
t4t1
s1
s4
t3
︸ ︷︷ ︸
C̄12
s3
s2
t′2
t′4t1
s1
s′4
t′3
s3
s′2
s′3
L1 s2
t̄2
t̄4t1
s1
s′4
t̄3
s3
s′2
s′3
L1
s̄2
s̄4
s̄3
(a) (b) (c)
Figure 3: Auxiliary figure for Case 2 (a) This shows a scenario where d1 = 5, d2 = 3, and
α = 2. (b) The path L1 = s1−t1 in dashed line, the paths that send the terminals in B1\B3
other than s1 and t1 to B3, and the resulting new linkage Y ′ = {{s′2, t′2}, {s′3, t′3}, {s′4, t′4}}
in C̄12 ∪ Bα+1. (c) The paths that send the terminals in B3 to A3, and the resulting new
linkage Y ′′ = {{s̄2, t̄2}, {s̄3, t̄3}, {s̄4, t̄4}} in C̄12.
Next we show how to send to Bα+1 the terminals other than s1 and t1 that are in the
rows 2 to α + 1 of C12; that is, the terminals other than s1 and t1 that are in B1 \ Bα+1.
For α = 0, B1 \ Bα+1 = ∅ and there is nothing to do. We now focus on the subcase
2 ≤ α ≤ d1 − 2. Let n1 and n2 denote the number of terminals in B1 \ Bα+1 and Bα+1,
respectively. Then the following inequalities hold
n1 + n2 ≤ d1 + 2− α ≤ d1 (since 2 ≤ α),
n1 + n2 ≤ d1 + 2− α ≤ 2d1 − 2α = |V (Bα+1)| (since α ≤ d1 − 2).
From the second inequality, it follows that there are at least n1 free vertices in Bα+1. Since
B1 is d1-connected by Lemma 2.5, Menger’s theorem gives n1 disjoint paths in B1 from the
terminals in B1 \Bα+1 to n1 free entries in Bα+1, avoiding the n2 terminals in Bα+1. For
a terminal si in B1 \Bα+1, let L′i be the path from si to Bα+1 and let s′i := V (L′i)∩Bα+1.
Define t′i similarly for a terminal ti in B1 \ Bα+1. Furthermore, for si (respectively, ti) in
L. K. Jørgensen et al.: Linkedness of Cartesian products of complete graphs 325
Bα+1 ∪ C̄12, let s′i := si (respectively, t′i := ti). This produces a new linkage problem
Y ′ := {{s′2, t′2}, . . . , {s′k, t′k}} in C̄12 ∪Bα+1. See Figure 3(b).
There are at most d1 + 2 − α terminals in Bα+1 = Kd1−α × K2, and every row
in Aα+1 = Kd1−α × Kd2−1 has a free entry. Hence, Claim 2.10 applies, and there
is a linkage formed by X-valid paths from the terminals in Bα+1, other than s1 and
t1, to free entries in Aα+1. For every such path L′′i , if s
′
i ∈ V (L′′i ) ∩ V (Bα+1), let
{s̄i} := V (L′′i )∩V (Aα+1), and if t′i ∈ V (L′′i )∩V (Bα+1), let {t̄i} := V (L′′i )∩V (Aα+1).
Besides, for s′i ∈ C̄12 (respectively t′i ∈ C̄12), let s̄i = s′i (respectively, t̄i = t′i). This pro-
duces a new linkage problem Y ′′ := {{s̄2, t̄2}, . . . , {s̄k, t̄k}} in C̄12 whose feasibility
implies that of Y ′, and therefore that of Y in G, by completing each linkage problem with
the path L1. See Figure 3(c).
Now we have a new linkage problem Y ′′ in C̄12 with (k− 1) pairs. The solution of Y ′′
in C̄12 implies a solution of the linkage problem Y in G. To link the pairs of Y ′′ use the
(k − 1)-linkedness of C̄12.
Finally assume that α = 1. Then there are exactly d1 + 1 terminals in C12 and at most
d2 − 1 terminals in C̄12. In a first scenario suppose that either both entries in B1 \ B2 are
nonterminals or each terminal other than s1 and t1 in B1 \B2 is adjacent to a nonterminal
in B2. Then we can send these terminals in B1 \B2 to B2. In the second scenario, suppose
that there is a terminal si (i ̸= 1) in B1 \ B2 whose neighbours in B2 are all terminals.
Then the column of si in B1 would contain exactly d1 terminals, including si. We send si
to a free entry in A1, in the same row as si (the first row of A1): if this free entry didn’t
exist, then si would be adjacent to the d2 − 1 terminals in A1 and the d1 − 1 terminals in
B2. Since there are d1 + d2 terminals in total, it would follow that si is adjacent to ti. This
contradiction shows that we can send si to a free entry in A1.
In both scenarios, it remains to send the terminals other than s1 and t1 in B2 = Kd1−1×
K2 to A2 = Kd1−1 ×Kd2−1. To do so, we reason as in the subcase 2 ≤ α ≤ d1 − 2. It
follows that there are at most d1 + 2 − 1 terminals in B2, and that every row in A2 has a
free entry. Claim 2.10 applies again and gives a linkage formed by X-valid paths from the
terminals in B2, other than s1, t1, to free entries in A2.
With all the terminals other than s1 and t1 in C̄12, therein we have a new linkage
problem Y ′ with k−1 pairs whose solution in C̄12 implies a solution of the linkage problem
Y in G. To solve Y ′ in C̄12 use the (k − 1)-linkedness of C̄12.
By symmetry, we also have the result if there are at most d2 + 2 terminals in R12,
including {s1, t1}.
Case 1. The subgraph C12 contains at least d1 + 3 terminals, including {s1, t1}.
This case reduces to the previous case. If C12 contains at least d1 + 3 terminals then
R12 contains at most d2 − 3 + 4 = d2 + 1 terminals, since there are four entries shared
by C12 and R12. Because we make no distinction between columns and rows, this case is
already covered. This completes the proof of the theorem.
3 Duals of cyclic polytopes
There is a close connection between duals of cyclic d-polytopes with d + 2 vertices and
Cartesian products of complete graphs.
The moment curve in Rd is defined by x(t) := (t, t2, . . . , td) for t ∈ R, and the convex
hull of any n > d points on it gives a cyclic polytope C(n, d). The combinatorics of a cyclic
326 Ars Math. Contemp. 22 (2022) #P2.09 / 317–326
polytope, the face lattice of the polytope faces partially ordered by inclusion, is independent
of the points chosen on the moment curve. Hence we talk of the cyclic d-polytope on n
vertices [6, Example 0.6].
For a polytope P that contains the origin in its interior, the dual polytope P ∗ is defined
as
P ∗ = {y ∈ Rd | x · y ≤ 1 for all x in P}.
If P does not contain the origin, we translate the polytope so that it does. Translating the
polytope P changes the geometry of P ∗ but not its face lattice. The face lattice of P ∗ is
the inclusion reversed face lattice of P . In particular, the vertices of P ∗ correspond to the
facets of P , and the edges of P ∗ correspond to the (d− 2)-faces of P . The dual graph of a
polytope P is the graph of the dual polytope, or equivalently, the graph on the set of facets
of P where two facets are adjacent in the dual graph if they share a (d− 2)-face.
Duals of cyclic d-polytopes are simple d-polytopes. It is also the case that the dual
of a cyclic d-polytope with d + 2 vertices can be expressed as T (⌊d/2⌋) × T (⌈d/2⌉)
([6, Example 0.6]). From this observation and Theorem 2.1 the next corollary follows
at once.
Corollary 3.1. Duals of cyclic polytopes with d + 2 vertices are ⌊d/2⌋-linked for every
d ≥ 2.
ORCID iDs
Leif K. Jørgensen https://orcid.org/0000-0003-4922-3937
Guillermo Pineda-Villavicencio https://orcid.org/0000-0002-2904-6657
Julien Ugon https://orcid.org/0000-0001-5290-8051
References
[1] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer-Verlag,
Berlin, 5th edition, 2017, doi:10.1007/978-3-662-53622-3.
[2] S. Gallivan, Disjoint edge paths between given vertices of a convex polytope, J. Comb. Theory
Ser. A 39 (1985), 112–115, doi:10.1016/0097-3165(85)90086-x.
[3] J. E. Goodman and J. O’Rourke (eds.), Handbook of Discrete and Computational Geometry,
Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 1997,
http://www.csun.edu/˜ctoth/Handbook/HDCG3.html.
[4] G. Mészáros, On linkedness in the Cartesian product of graphs, Period. Math. Hungar. 72 (2016),
130–138, doi:10.1007/s10998-016-0113-8.
[5] S. Špacapan, Connectivity of Cartesian products of graphs, Appl. Math. Lett. 21 (2008), 682–
685, doi:10.1016/j.aml.2007.06.010.
[6] G. M. Ziegler, Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics, Springer-
Verlag, New York, 1995, doi:10.1007/978-1-4613-8431-1.