Reconstruction of the Geometric Structure of a Set of Points in the Plane from Its Geometric Tree Graph

Abstract

Let P be a finite set of points in general position in the plane. The structure of the complete graph K(P) as a geometric graph includes, for any pair [a, b], [c, d] of vertex-disjoint edges, the information whether they cross or not. The simple (i.e., non-crossing) spanning trees (SSTs) of K(P) are the vertices of the so-called Geometric Tree Graph of P, G(P). Two such vertices are adjacent in G(P) if they differ in exactly two edges, i.e., if one can be obtained from the other by deleting an edge and adding another edge. In this paper we show how to reconstruct from G(P) (regarded as an abstract graph) the structure of K(P) as a geometric graph. We first identify within G(P) the vertices that correspond to spanning stars. Then we regard each star S(z) with center z as the representative in G(P) of the vertex z of K(P). (This correspondence is determined only up to an automorphism of K(P) as a geometric graph.) Finally we determine for any four distinct stars S(a), S(b), S(c),  and S(d), by looking at their relative positions in G(P), whether the corresponding segments cross.

1 Introduction

Graph reconstruction is an old and extensive research topic. It dates back to the Reconstruction Conjecture raised by Kelly and Ulam in 1941 (see [8, 12]), which asserts that every graph on at least three vertices is uniquely determined by its collection of vertex deleted subgraphs.

As a natural extension of the Reconstruction Conjecture, numerous papers considered either reconstruction of structures other than graphs (a research topic proposed by Ulam in 1960), or reconstructions of graphs from other information. In the first direction, reconstructed objects include colored graphs, hypergraphs, matroids, relations, and other classes. In the second direction, the “information” may be k-vertex deleted subgraphs, edge-deleted subgraphs, elementary contractions, spanning trees, etc. In addition, various papers considered reconstruction of parameters of the graph instead of its full structure. Such parameters include the order, the degree sequence, planarity, the types of spanning trees, and many others (see the surveys [2, 10] for references).

In this paper, we study the problem of reconstructing the geometric structure of a set of points in the plane from its geometric tree graph.

Tree graphs were defined in 1966 by Cummins [3] in the context of listing all spanning trees of a given connected graph effectively. The tree graph T(G) of a graph G has the spanning trees of G as its vertices, and two spanning trees are adjacent if one can be obtained from the other by deleting an edge and adding another edge. These graphs were studied in a number of papers and were shown to be Hamiltonian and to have the maximal possible connectivity (see, e.g., [7, 9]).

In 1996, Avis and Fukuda [1] defined the geometric tree graph, as the counterpart of tree graphs in the geometric graph setting.

Definition 1.1

Let P be a finite point set in general position in the plane. The geometric tree graph G(P) is defined as follows. The vertices of G(P) are the simple (i.e., non-crossing) spanning trees (SSTs) of K(P). Two such vertices are adjacent in G(P) if they differ in exactly two edges, i.e., if one can be obtained from the other by deleting an edge and adding another edge.

Geometric tree graphs were shown to be connected [1], and upper and lower bounds on their diameter were established [1, 6].

We study a reconstruction problem for geometric graphs: Is the geometric tree graph G(P) sufficient for “reconstructing” the structure of K(P)? In a sense, this question is a geometric counterpart of the work of Sedláček [11], who studied the question whether a graph can be reconstructed from its spanning trees. As we deal with a geometric setting, we seek to reconstruct the geometric structure of the graph.

Definition 1.2

Let P be a finite set of points in general position in the plane. The geometric structure of the complete graph K(P) as a geometric graph includes, for any pair [a, b], [c, d] of vertex-disjoint edges, the information whether they cross or not.

Our main result is the following:

Theorem 1.3

For any finite set P of points in general position in the plane, the geometric structure of K(P) can be reconstructed from the geometric tree graph G(P).

While the proof of the theorem is elementary, it is rather complex, and consists of several stages:

• 1. Maximal cliques in G(P). We study thoroughly the structure of maximal cliques in G(P). We divide these cliques into two types, called “union max-cliques” and “intersection max-cliques”, and show that given a maximal clique in G(P), one can determine its type. This study spans Sect. 2.

• 2. Stars and brushes in G(P). We show how to identify the vertices of G(P) that correspond to spanning stars and spanning brushes (i.e., spanning trees of diameter 3 with a single internal edge), by examining the max-cliques to which they belong. The stars are determined only up to an automorphism of K(P) (obviously, one cannot do better), and once they are fixed, the brushes are determined uniquely. This part of the proof is presented in Sect. 3.

• 3. The geometric structure of K(P). We show how the geometric structure of K(P) can be derived from information on the brushes in G(P). This part is presented in Sect. 4.

In the last part of the paper, Sect. 5, we consider abstract (i.e., non-geometric) graphs, and show that a variant of the argument developed in Sects. 2 and 3 can be used to prove the following result:

Theorem 1.4

For any $n \in \mathbb {N}$, the automorphism group of the tree graph of $K_n$ is isomorphic to $\mathrm {Aut}(K_n) \cong S_n$.

Our treatment of the geometric reconstruction problem (i.e., K(P) from G(P)) falls short of this. It leaves open the (quite implausible) possibility that the geometric tree graph G(P) has an automorphism $\eta$, other than the identity, that fixes each star and each brush. This leaves open, for further research, the following question.

Question 1.5

Is it true that for any finite set P of points in general position in the plane, we have $\mathrm {Aut}(G(P)) \cong \mathrm {Aut}(K(P))$, where G(P) is treated as an abstract graph, whereas K(P) is treated as a geometric graph?

2 Maximal Cliques in G(P)

In this section we study the structure of maximal (with respect to inclusion) cliques in the geometric tree graph G(P). We divide the maximal cliques into two types, called U-cliques and I-cliques, and our ultimate goal is to determine, given a maximal clique in G(P), what is its type.

We start in Sect. 2.1 with a few definitions and notations, to be used throughout the paper. In Sects. 2.2 and 2.3 we describe a classification of the maximal cliques into two types, presented originally in [13], and discuss basic properties of both types. In order to distinguish between general combinatorial considerations and geometric arguments specific to SSTs, we start in Sect. 2.2 with a general combinatorial framework, and leave the geometric arguments to Sect. 2.3.

In Sects. 2.4 and 2.5 we study degenerate maximal cliques, i.e., maximal cliques of size 2. In Sect. 2.4 we give a geometric characterization of the situation when a maximal clique is degenerate, and in Sect. 2.5 we show how to identify whether a given degenerate maximal clique is a U-clique or an I-clique. Finally, in Sect. 2.6 we show how to determine whether a given non-degenerate maximal clique is a U-clique or an I-clique.

2.1 Definitions and Notations

Notation 2.1

The following notations and conventions are used throughout the paper. The straight line that passes through points x, y is denoted by $\ell (x,y)$. The vertex and edge sets of a graph G are denoted by V(G) and E(G), respectively. Since the set P is fixed, we shall always identify a spanning subgraph of K(P) (and, in particular, a spanning subtree) with its set of edges.

In our study we shall extensively use maximal cliques of G(P). These are defined as follows:

Definition 2.2

A max-clique in a graph G is a maximal (with respect to inclusion) clique included in G. Since any max-clique is a complete graph on its vertex set, we shall identify a max-clique with its set of vertices.

We shall use the following observation on the structure of G(P), proved by Avis and Fukuda [1].

Claim 2.3

([1, Lem. 3.15]) For any set P of points in general position in the plane, G(P) is connected and its diameter is $\le 2|P|-4$.

2.2 Types of Max-Cliques in Tree Graphs

A generic combinatorial way to treat a tree graph is to consider a base set X and a graph G whose vertices are q-subsets of X (not necessarily all the q-subsets), such that two vertices $A, B \in V(G)$ are adjacent if and only if $|A \triangle B|=2$. (In the case of the (geometric) tree graph of a point set P, we have $X=E(K(P))$, $q=|P|-1$, and the vertices of G are the sets of edges of (simple) spanning trees of K(P).)

Let A, B be two adjacent vertices of G. Denote

$$\begin{aligned} I=A \cap B, \qquad D = A \triangle B \qquad \text{ and } \qquad U = A \cup B = I \cup D. \end{aligned}$$

A third vertex $C \in V(G)$ is a common neighbor of A and B if and only if:

• 1. $C \cap D = \emptyset$ and $I \subset C$. In this case, C is obtained from I by adding a single element.

• 2. $D \subset C$ and $C \subset U$. In this case, C is obtained from U by removing a single element.

(It is easy to see that in any other case, either $|A \triangle C| \ne 2$ or $|B \triangle C| \ne 2$.)

If $C,C'$ are both common neighbors of A and B, such that C satisfies (1) and $C'$ satisfies (2), then clearly, $|C \triangle C'|=4$. Hence, if two common neighbors of A and B are themselves neighbors, then either both satisfy (1) or both satisfy (2). On the other hand, it is clear that any two common neighbors satisfying (1) are themselves neighbors, and the same holds for (2). Thus, any pair A, B of adjacent vertices of G is included in at most two max-cliques:

• 1. $U(A,B) = \{C \in V(G) | C \subset A \cup B\}$, and

• 2. $I(A,B) = \{C \in V(G) | C \supset A \cap B\}$.

For any two elements $C,C' \in U(A,B)$, the union $C \cup C'$ is constant (and equal to U). Likewise, for any two elements $C,C' \in I(A,B)$, the intersection $C \cap C'$ is constant (and equal to I). This is the motivation behind the following definition.

Definition 2.4

A max-clique of the first type will be called a Union max-clique, or a U-clique, and a max-clique of the second type will be called an Intersection max-clique or an I-clique.

Remark 2.5

It is clear that given two vertices A, B of a max-clique C, we cannot determine whether C is a U-clique or an I-clique. However, if we are given a third vertex $B' \in C$, we can determine the type, according to which one of the equalities $A \cap B = A \cap B'$, $A \cup B = A \cup B'$ holds. Moreover, once we determine that C is, say, an I-clique, we know that $C=I(A,B)$ as this is the unique I-clique that includes A and B. Hence, three vertices of a max-clique determine it uniquely.

Definition 2.6

If $U(A,B)=\{A,B\}$, we say that $\{A,B\}$ is a degenerate U -clique. Similarly, if $I(A,B)=\{A,B\}$, we say that $\{A,B\}$ is a degenerate I -clique.

For a pair of adjacent vertices A, B, there are four possible situations:

• 1. $|U(A,B)| \ge 3$ and $|I(A,B)| \ge 3$. In this case, there are exactly two max-cliques that contain A and B.

• 2. $|U(A,B)| \ge 3$ and $|I(A,B)| = 2$. In this case, there is a unique max-clique that contains A and B, namely U(A, B). (The I-clique that contains A and B is degenerate.)

• 3. The same as (2), with the roles of U(A, B) and I(A, B) interchanged.

• 4. $U(A,B) = I(A,B) = \{A,B\}$. In this case, the set $\{A,B\}$ itself is a max-clique (that is, both a U-clique and an I-clique). As we shall see in the sequel, this situation cannot occur in our geometric setting.

2.3 Types of Max-Cliques in G(P)

Now we turn to the geometric tree graph G(P) and show additional properties of max-cliques that follow from its geometric structure. In order to make our notation suggestive, we denote now the two adjacent vertices of G(P) by $T_1,T_2$, and the edges in their symmetric difference by $e_1 \in T_1 \setminus T_2$ and $e_2 \in T_2 \setminus T_1$.

In G(P), U-cliques and I-cliques have a geometric meaning.

• 1. $U(T_1,T_2)$. Consider the graph $\bar{T} = T_1 \cup T_2 = T_1 \cup \{e_2\}$. Obviously, it is a connected graph with a unique cycle. This cycle contains $e_1$ and $e_2$, and is simple if and only if $e_1$ and $e_2$ do not cross. (Note that $e_2$ cannot cross another edge of $T_1$, as both these edges belong to the SST $T_2$.) As shown above, $U(T_1,T_2)$ consists of all vertices of G(P) that are obtained from $\bar{T}$ by removing a single edge. Since the vertices of G(P) are the edge sets of SSTs, we can say that removing an edge (other than $e_1,e_2$) from $\bar{T}$ results in an element of $U(T_1,T_2)$ if and only if the unique cycle of $\bar{T}$ is simple, and the removed edge belongs to that cycle. Note that if $e_1,e_2$ cross, then removal of any edge other than $e_1,e_2$ from $\bar{T}$ results in a non-simple graph, and thus, the only elements of $U(T_1,T_2)$ are $T_1$ and $T_2$.

• 2. $I(T_1,T_2)$. Consider the graph $\tilde{T} = T_1 \cap T_2 = T_1 \setminus \{e_1\}$. Obviously, it is a simple forest with two connected components. As shown above, $I(T_1,T_2)$ consists of all vertices of G(P) that are obtained from $\tilde{T}$ by adding a single edge. Since the vertices of G(P) are the edge sets of SSTs, we can say that adding an edge to $\tilde{T}$ results in an element of I(A, B) if and only if that edge makes the forest $\tilde{T}$ into a simple spanning tree of K(P).

2.4 Geometric Characterization of Degenerate Cliques

The geometric interpretation allows us to characterize the cases when U-cliques and I-cliques are degenerate.

Claim 2.7

Let P be a finite set of points in the plane, no three on a line, $|P| \ge 4$. Let $T_1,T_2$ be SSTs of K(P) such that $T_1 \setminus T_2 = \{e_1\}$ and $T_2 \setminus T_1 = \{e_2\}$. The U-clique $U(T_1,T_2)$ is degenerate if and only if $e_1$ and $e_2$ cross.

Proof

By the geometric interpretation, if $e_1$ and $e_2$ cross then the only vertices of $U(T_1,T_2)$ are $T_1$ and $T_2$, and thus, it is degenerate. If $e_1$ and $e_2$ do not cross, then $\bar{T}$ is a simple connected graph on n vertices with n edges. (Note that $\bar{T}$ is simple since as $T_1,T_2$ are SSTs, the only edges in $\bar{T}$ that may cross each other are $e_1,e_2$.) Thus, $\bar{T}$ has a cycle of order at least 3. Removal of any edge from this cycle gives rise to a vertex in $U(T_1,T_2)$. Therefore, in this case $U(T_1,T_2)$ is non-degenerate. $\square$

Proposition 2.8

Let P be a finite set of points in the plane, no three on a line, $|P| \ge 4$. Let $T_1,T_2$ be SSTs of K(P) such that $T_1 \setminus T_2 = \{e_1\}$ and $T_2 \setminus T_1 = \{e_2\}$. The I-clique $I(T_1,T_2)$ is degenerate only in the following case:

The convex polygon $\mathrm {conv}(P)$ has three consecutive vertices x, v, y (i.e., [x, v] and [v, y] are edges of $\mathrm {conv}(P)$), such that:

• 1. The triangle $\mathrm {conv}(x,v,y)$ contains no other points of P.

• 2. $e_1 = [x,v]$ and $e_2 = [v,y]$.

• 3. $[x,y] \in T_1 \cap T_2$.

Fig. 1

Illustration to the proof of Proposition 2.8

Proof

Assume that (1)–(3) hold, and let $T_0 \in I(T_1,T_2)$. $T_0$ is connected, and thus, has an edge e that emanates from v. Note that as x, v, y are consecutive vertices of $\mathrm {conv}(P)$ and the triangle $\mathrm {conv}(x,v,y)$ contains no other points of P, any edge of K(P) that emanates from v (other than $e_1$ and $e_2$) must cross [x, y]. Thus, either $e=e_1$, $e=e_2$, or e crosses [x, y]. The latter is impossible, since $[x,y] \in T_1 \cap T_2$, and as shown above, $T_1 \cap T_2$ is included in any element of $I(T_1,T_2)$. If $e=e_1$, then $T_1 = ((T_1 \cap T_2) \cup \{e_1\}) \subset T_0$, which implies $T_0=T_1$ (as both have the same number of edges). Similarly, if $e=e_2$ then $T_0=T_2$. Therefore, the only elements of $I(T_1,T_2)$ are $T_1$ and $T_2$, i.e., $I(T_1,T_2)$ is degenerate.

In the other direction, assume that $I(T_1,T_2)$ is degenerate. As mentioned above, the graph $\tilde{T}=T_1 \cap T_2$ is a simple forest with two connected components. Color the vertices of one component white and the vertices of the other component black, and call an edge colorful if its endpoints are of different colors.

Since $\tilde{T}$ is planar, it can be extended to a triangulation ${\mathcal {T}}$ of $\mathrm {conv}(P)$ with vertex set P. As ${\mathcal {T}}$ is connected, it contains a colorful edge e. A triangle in ${\mathcal {T}}$ to which e belongs clearly contains another colorful edge $e'$. Addition of either e or $e'$ to $\tilde{T}$ results in a simple tree, and thus, gives rise to a vertex of $I(T_1,T_2)$. (Note that e and $e'$ cannot cross edges of $\tilde{T}$ since they belong to a triangulation that extends $\tilde{T}$.) Since $I(T_1,T_2)$ is degenerate, this implies that all other edges of ${\mathcal {T}}$ are not colorful. We claim that this can happen only in the case described in the statement of the proposition.

Consider the edges $e,e'$. If e is not a boundary edge of $\mathrm {conv}(P)$ then it belongs to another triangle in ${\mathcal {T}}$. The other triangle must contain an additional colorful edge, contradicting the assumption that only e and $e'$ are colorful. The same holds for $e'$, and thus, both e and $e'$ are boundary edges of $\mathrm {conv}(P)$. Denote their common vertex by v and their other endpoints by x, y, respectively.

It is clear that Condition (1) above holds for x, v, y, since ${\mathcal {T}}$ is a triangulation of P and $\mathrm {conv}(v,x,y)$ is one of its triangles. To see that Condition (2) holds, note that $\tilde{T} \cup \{e\}$ and $\tilde{T} \cup \{e'\}$ are the only vertices of $I(T_1,T_2)$, and thus, are equal to $T_1$ and $T_2$. As $T_i=\tilde{T} \cup \{e_i\}$ for $i=1,2$, the edges $e,e'$ must coincide with $e_1$ and $e_2$.

Finally, since $|P| \ge 4$, [x, y] is a diagonal of $\mathrm {conv}(P)$, and thus, in the triangulation ${\mathcal {T}}$ it belongs to another triangle $\mathrm {conv}(x,y,w)$ (see Fig. 1). This triangle is monochromatic (as otherwise, there are at least four colorful edges in ${\mathcal {T}}$), hence w, v are of different colors. We apply a flip to the triangulation ${\mathcal {T}}$, replacing the triangles $\mathrm {conv}(x,y,v), \mathrm {conv}(x,y,w)$ by $\mathrm {conv}(x,v,w),\mathrm {conv}(y,v,w)$. The resulting triangulation includes an additional colorful edge [v, w] that does not cross any edge of $\tilde{T}$, except possibly for [x, y]. Since by assumption, there are only two colorful edges that do not cross edges of $\tilde{T}$, we must have $[x,y] \in \tilde{T}$, which means that Condition (3) holds. $\square$

Corollary 2.9

Each edge of G(P) is contained in at least one non-degenerate max-clique.

Proof

Let $[T_1,T_2] \in G(P)$ ¹ and denote $T_1 \setminus T_2 = \{e_1\}$ and $T_2 \setminus T_1 = \{e_2\}$. If $e_1,e_2$ do not cross then $U(T_1,T_2)$ is non-degenerate by Claim 2.7. If $e_1,e_2$ cross then $I(T_1,T_2)$ is non-degenerate, since by the proof of Proposition 2.8, if $I(T_1,T_2)$ is degenerate, then the only edges that can be added to $T_1 \cap T_2$ to form a simple tree share a vertex, which is not the case for $e_1,e_2$ that cross in an interior point. $\square$

2.5 Identification of the Type of a Degenerate Clique in G(P)

Lemma 2.10

Let T be an SST of G(P), and let D be an I-clique that contains T. Denote the common intersection of pairs of elements of D by $\tilde{T}$, and let $\{e\}=T \setminus \tilde{T}$. If e is not a leaf edge of T, then $|V(D)| \ge 4$.

Fig. 2

Illustration to Case 1 of Lemma 2.10

Proof

We begin the proof with the argument used in the proof of Proposition 2.8. Namely, we consider the graph $\tilde{T}$, which is a simple forest with two components. We color its components black and white, and extend it to a triangulation ${\mathcal {T}}$ of P. The triangulation contains a colorful edge [a, b], and consequently, another colorful edge $[a,b']$ in the same triangle. Assume w.l.o.g. that a is black, b and $b'$ are white.

Now we would like to use the assumption that e is not a leaf edge of T. This assumption implies that each connected component of $\tilde{T}$ has at least two vertices. Consequently, any vertex $v \in P$ is an endpoint of at least one monochromatic edge of ${\mathcal {T}}$ (as otherwise, v would be isolated in $\tilde{T}$).

If both [a, b] and $[a,b']$ are boundary edges of $\mathrm {conv}(P)$, then (since $\triangle a,b,b'$ is a triangle in ${\mathcal {T}}$) these are the only edges of ${\mathcal {T}}$ that emanate from a. This is impossible, as they are both colorful. Hence, we can assume w.l.o.g. that [a, b] is a diagonal edge of $\mathrm {conv}(P)$, and thus, belongs to two triangles, $\triangle abc$ and $\triangle abd$. (Note that either c or d is equal to the vertex $b'$ mentioned above.) We consider several cases, according to the colors of c and d:

• 1. Case 1: c and d are white. (This case is illustrated in Fig. 2.) Consider the neighbors of a in ${\mathcal {T}}$. Since ${\mathcal {T}}$ is a triangulation, all these vertices lie on a path in ${\mathcal {T}}$. As stated before, since a is black, at least one of its neighbors must be black. On the other hand, some of its neighbors (including b, c, d) are white. Hence, at least one of the edges in the path connecting the neighbors of a is colorful (see Fig. 2). In addition, the edges [a, b], [a, c], [a, d] are colorful. Thus, ${\mathcal {T}}$ contains at least four colorful edges, and each of them gives rise to a vertex of D. Therefore, $|V(D)| \ge 4$.

• 2. Case 2: c and d are black. Since the black vertices a, c, d are all neighbors of the white vertex b, the argument of Case 1 applies, with the roles of a with b, black and white, interchanged.

• 3. Case 3: c and d have different colors. Assume w.l.o.g. that c is white and d is black. In this case, the edges [a, b], [a, c],  and [b, d] are colorful. We further divide this case into three subcases, according to whether [a, c] and [b, d] are diagonal edges of $\mathrm {conv}(P)$ or not, and show that in each case, ${\mathcal {T}}$ contains at least one additional colorful edge.

  • (a) Case 3a: [b, d] is a diagonal edge of $\mathrm {conv}(P)$. In this case, [b, d] belongs to an additional triangle of ${\mathcal {T}}$ (i.e., other than $\triangle abd$). If this triangle is $\triangle bdc$, then the edge [c, d] is colorful, implying $|V(D)| \ge 4$ (see left part of Fig. 3). If this triangle is $\triangle bdk$ for some $k \ne c$, then, as b and d have different colors, one of the edges [b, k] and [d, k] is colorful, again implying $|V(D)| \ge 4$ (see right part of Fig. 3).

  • (b) Case 3b: [a, c] is a diagonal edge of $\mathrm {conv}(P)$. The argument of Case 3a applies, with the roles of a and b, c and d, black and white, interchanged.

  • (c) Case 3c: Both [a, c] and [b, d] are boundary edges of $\mathrm {conv}(P)$. In this case, $\square acbd$ is a convex quadrilateral, and thus, its diagonal [c, d] lies inside it (see Fig. 4). As both $\triangle abc$ and $\triangle abd$ are triangles in ${\mathcal {T}}$, they do not contain points of P, hence [c, d] does not cross any edge of $\tilde{T}$. (Note that [a, b] is not an edge of $\tilde{T}$, since it is colorful.) Since [c, d] is colorful, the graph $\tilde{T} \cup \{[c,d]\}$ is an SST, hence belongs to D. Therefore, $|V(D)| \ge 4$, which completes the proof of the lemma.$\square$

Fig. 3

Illustrations to Case 3a of Lemma 2.10

Fig. 4

Illustration to Case 3c of Lemma 2.10

Using the lemma, we can identify whether a given degenerate clique is a U-clique or an I-clique.

Proposition 2.11

Let [S, T] be an edge in G(P) that constitutes a degenerate clique. (This actually means that there is only one max-clique that includes $\{S,T\}$.) If [S, T] is included in a max-clique of 3 vertices, then the degenerate clique [S, T] is an I-clique. If [S, T] is included in a max-clique of at least 4 vertices, then the degenerate clique [S, T] is a U-clique.

Proof

By Corollary 2.9, each edge is included in at least one non-degenerate max-clique. Hence, [S, T] is included in a max-clique of size at least 3.

If the degenerate clique [S, T] is an I-clique, then, by Proposition 2.8, $S \cap T$ is a forest with two connected components. One of them is an isolated vertex v that lies on the boundary of $\mathrm {conv}(P)$, and the two neighbors of v on the boundary of $\mathrm {conv}(P)$, x, y, are adjacent in $S \cap T$. In such a case, the unique cycle in the graph $S \cup T$ is the triangle $\triangle (x,v,y)$. By the geometric characterization of Sect. 2.3, this implies that the size of the U-clique that includes [S, T] is 3.

If the degenerate clique [S, T] is a U-clique, then, by Claim 2.7, the unique cycle of $S \cup T$ includes the edges $s \in S \setminus T$ and $t \in T \setminus S$, and these edges cross. This implies that s is not a leaf edge of S, and thus, by Lemma 2.10, the size of the I-clique that includes [S, T] is at least 4. $\square$

2.6 Identification of the Type of a Non-degenerate Max-Clique in G(P)

Our next goal is to identify whether a given non-degenerate max-clique is a U-clique or an I-clique. This identification is somewhat more complex, and requires some preparations.

Definition 2.12

For any SST $T \in G(P)$, define a graph $D_T$ as follows: V(T) is the set of max-cliques that contain T (including degenerate cliques). Two max-cliques are adjacent in $D_T$ if and only if their intersection is a single edge (that obviously has T as one of its endpoints).

Note that by Remark 2.5, two non-identical max-cliques may intersect in at most two vertices (since three mutually adjacent vertices determine a max-clique uniquely). As all vertices of $D_T$ include T, it follows that any two non-adjacent vertices of $D_T$ intersect in T only.

Theorem 2.13

Assume that $|P| \ge 5$. For any $T \in G(P)$, the graph $D_T$ is connected.

Before we present the proof of the theorem, we show how it can be used (along with several of the previous lemmas) to identify the types of max-cliques in G(P).

By the discussion in Sect. 2.2, each edge of G(P) belongs to exactly one U-clique and exactly one I-clique (one of them possibly degenerate). This implies that $D_T$ is 2-colorable. Indeed, we can color all its vertices that are U-cliques white and all its vertices that are I-cliques black. If two vertices are adjacent, both include the same edge $[S,T] \in G(P)$, and thus, one is a U-clique and the other is an I-clique, so they have different colors. Using Theorem 2.13, we can conclude that $D_T$ is connected and 2-colorable, which implies that the 2-coloring is unique, in the sense that fixing the color of any vertex determines the colors of all other vertices. This will allow us to determine the types of all max-cliques, by the following four-step process:

• 1. Pick an SST T that belongs to a degenerate clique $\{S,T\}$. (It is easy to show that such a T always exists. We show this in Lemma 2.14 below.) Using Proposition 2.11, identify whether $\{S,T\}$ is a U-clique or an I-clique.

• 2. Consider the vertices of $D_T$ and determine for each of them whether it is a U-clique or an I-clique. (This is possible by the explanation above. Since we know the “color” of the vertex $\{S,T\}$ of $D_T$, we can determine the colors of all other vertices.)

• 3. Consider a neighbor $T'$ of T. Note that the edge $[T,T'] \in G(P)$ belongs to a max-clique C that is a vertex of both $D_T$ and $D_{T'}$. Determine whether C is a U-clique or an I-clique. (This is possible, as by the previous step we can determine the type for all max-cliques that are vertices of $D_T$.) Using this information about $C \in V(D_{T'})$, determine for each vertex of $D_{T'}$ whether it is a U-clique or an I-clique.

• 4. Repeat Step 3 with a “new” vertex of G(P) every time until the types of all max-cliques are determined. (Since G(P) is connected by Claim 2.3, we indeed reach all vertices of G(P) in this way.)

Therefore, in order to determine the types of all max-cliques we have to prove a simple lemma on the existence of degenerate max-cliques, and to prove Theorem 2.13. We provide these two items now.

Lemma 2.14

For any set P, $|P| \ge 5$, of points in general position in the plane, there exists an SST that belongs to a degenerate U-clique in G(P).

Fig. 5

An illustration for the proof of Lemma 2.14

Proof

By the Erdős–Szekeres theorem [4], there exist four points in P in convex position. Denote these points a, b, c, d, such that [a, b, c, d] is a convex quadrilateral (in this order). Consider the tree T that includes the edges [a, b], [b, d], [d, c], all edges that connect a to each $p \in P$ that lies above the straight line $\ell (b,d)$ and all edges that connect c to each $p \in P$ that lies below $\ell (b,d)$, as shown in Fig. 5. Clearly, T is an SST of K(P). Addition of the edge [a, c] to T creates a self-crossing cycle, and thus, by the discussion in Sect. 2.3, $T \in V(G)$ belongs to a degenerate U-clique. $\square$

Proof of Theorem 2.13

Suppose $C,C' \in V(D_T)$. Choose edges $[T,S] \in C$, $[T,S'] \in C'$. In order to prove that C is connected to $C'$ by a path in $D_T$, it suffices to find a sequence $S^0,S^1,\ldots ,S^\ell$ of SST’s, such that $S^0=S$, $S^\ell =S'$, and for each $0 \le i< \ell$, there is a max-clique $C_i$ of G(P) that includes both $[T,S^i]$ and $[T,S^{i+1}]$. This will be done in four steps.

• 1. Step 1 Extend the SST T to a triangulation ${\mathcal {T}}$ of $\mathrm {conv}(P)$. Recall that ${\mathcal {T}}$ is a 2-connected graph.

• 2. Step 2 If $S \subset {\mathcal {T}}$, leave S as it is. If not, ${\mathcal {T}}$ contains the graph $\tilde{T}= T \cap S = T \setminus \{e\}$. Since ${\mathcal {T}}$ is 2-connected, there is another edge $e^{*}$ in ${\mathcal {T}}$ that connects the two components of $\tilde{T}$. Define $S^{*} = \tilde{T} \cup \{e^{*}\}$. $S^{*}$ is an SST of K(P). Note that $S^{*}$ is included in the I-clique I(T, S) (since $T \cap S^{*} = T \cap S = \tilde{T}$).

  Do the same for $S'$: leave it, if $S' \subset {\mathcal {T}}$, or replace it by some $S^{'*} \subset {\mathcal {T}}$, such that $S^{'*} \in I(T,S')$.

  Step 2 allows us to restrict our attention to the case where both S and $S'$ are included in ${\mathcal {T}}$ (and all intermediate SST’s will be included in ${\mathcal {T}}$, as well).

• 3. Step 3 Assume $T \cap S = T \setminus \{e\}$, $T \cap S' = T \setminus \{e'\}$. If $e=e'$, then [T, S] and $[T,S']$ belong to the same I-clique. Suppose $e \ne e'$. Since T is a simple tree, there is a unique simple path in T whose edges are (in this order) $e_1,e_2,\ldots ,e_m$, with $e_1=e$ and $e_m = e'$. For $1 <i <m$, choose an edge $e^*_i$ of ${\mathcal {T}}$ other than $e_i$ that connects the two components of $T \setminus \{e_i\}$, and define $S_i = T \setminus \{e_i\} \cup \{e^*_i\}$. In addition, let $S_1=S$ and $S_m=S'$. Now we only have to connect $S_{i-1}$ with $S_i$ for $i=2,3,\ldots ,m$. (Note that the desired sequence $S^0,S^1,\ldots ,S^\ell$ will be the concatenation of the sequences connecting $S_1$ to $S_2$, $S_2$ to $S_3$ etc., and $\ell$ will be the sum of their lengths.)

• 4. Step 4 Suppose ${\mathcal {T}}$ is a triangulation of $\mathrm {conv}(P)$ with vertex set P. Let $T,S,S'$ be SST’s of K(P) that are included in ${\mathcal {T}}$. Assume that both S and $S'$ are adjacent to T in G(P), $S \cap T = T \setminus \{e\}$, $S' \cap T = T \setminus \{e'\}$, $e \ne e'$, and $e,e'$ share a vertex. Suppose $e=[x,y], e'=[x',y]$, and let $k=\deg (y)-2$. Denote the edges of T that emanate from y by $e,e',f_1,f_2,\ldots ,f_k$. Removal of all edges that emanate from y divides T into $k+3$ connected components: D that includes x, $D'$ that includes $x'$, $F_s$ ($1 \le s \le k$) that includes the second endpoint of $f_s$, and $F_{k+1}$ that consists of the isolated vertex y. Since ${\mathcal {T}}$ is 2-connected, we can extend the forest $B= D \cup D' \cup F_1 \cup \cdots \cup F_k$ into an SST of $K(P \setminus \{y\})$ by adding $k+1$ edges of ${\mathcal {T}}$.

  Let $\bar{S}$ be such an extension. $\bar{S}$ includes a unique simple path $\pi$ from x to $x'$. This path starts in the component D of B, and ends in $D'$. It visits some of the intermediate components $F_i$ in a particular order (see Fig. 6). By appropriately labelling these components, we may assume that $\pi$ visits $D,F_1,F_2,\ldots ,F_l,D'$ in this order ($0 \le l \le k$). Let $g_0$ be the edge of $\pi$ that passes from D to $F_1$, $g_i$ ($1 \le i \le l-1$) the edge that passes from $F_i$ to $F_{i+1}$, and $g_l$ be the edge that passes from $F_l$ to $D'$. (If $l=0$, then there is only one edge $g=g_0$ that passes directly from D to $D'$.)

  Now we can describe the passage from [T, S] to $[T,S']$. Let us start with the simple case $l=0$. Put $S_1=T \setminus \{e\} \cup \{g\}$, $S_2 = T \setminus \{e'\} \cup \{g\}$. Then $T \cap S = T \cap S_1$, $T \cup S_1 = T \cup S_2$, and $T \cap S_2 = T \cap S'$. Thus, $\{T,S,S_1\}$ and $\{T,S_2,S'\}$ are included in I-cliques, while $\{T,S_1,S_2\}$ is included in a U-clique. Hence, $(S,S_1,S_2,S')$ is the required sequence.

  When $l>0$, define

  $$\begin{aligned}&S_1=T \setminus \{e\} \cup \{g_0\}, \qquad S_2=T \setminus \{f_1\} \cup \{g_0\}, \\&S_3=T \setminus \{f_1\} \cup \{g_1\}, \qquad S_4=T \setminus \{f_2\} \cup \{g_1\}, \\&\ldots \\&S_{2l-1}=T \setminus \{f_{l-1}\} \cup \{g_{l-1}\}, \qquad S_{2l}=T \setminus \{f_l\} \cup \{g_{l-1}\}, \\&S_{2l+1}=T \setminus \{f_l\} \cup \{g_l\}, \qquad \quad S_{2l+2}=T \setminus \{e'\} \cup \{g_l\}. \end{aligned}$$

  Then each of the triples $\{T,S,S_1\},\{T,S_{2i},S_{2i+1}\}$ (for $1 \le i \le l$), and $\{T,S_{2l+2},S'\}$ is included in an I-clique, and each of the triples $\{T,S_{2i-1},S_{2i}\}$ (for $1 \le i \le l+1$) is included in a U-clique. Therefore, $(S,S_1,S_2,\ldots ,S_{2l+1},S_{2l+2},S')$ is the required sequence. This completes the proof of the theorem.$\square$

Fig. 6

An illustration for the proof of Theorem 2.13

As explained after the statement of Theorem 2.13, the theorem and Lemma 2.14 imply the following corollary.

Corollary 2.15

Assume $|P| \ge 5$. Given G(P), we can determine for each max-clique in it whether it is a U-clique or an I-clique.

3 Identification of Stars and Brushes

In this section we use the results of Sect. 2 to identify the vertices of G(P) that represent stars (i.e., SSTs of diameter 2) and brushes (i.e., SSTs of diameter 3). The stars, considered in Sect. 3.1, are determined only up to an automorphism of K(P) as a geometric graph. The brushes, considered in Sect. 3.2, are determined uniquely given a determination of the stars.

3.1 Identification of Stars

Definition 3.1

A star is a tree of diameter 2.

Notation 3.2

For $x \in P$, we call the spanning star whose center is x an x -star, and denote it by S(x).

Theorem 3.3

A vertex $T \in G(P)$ is a star if and only if all U-cliques that include T are of size 3.

Proof

Recall that by the geometric interpretation of max-cliques presented in Sect. 2.3, if U(S, T) is a non-degenerate U-clique then all its elements are obtained from the graph $S \cup T$ by removing an edge from its unique cycle. In particular, |U(S, T)| is the length of the unique cycle of $S \cup T$. If the unique cycle of $S \cup T$ is self-crossing (which can occur only if its length is $\ge 4$) then U(S, T) is degenerate.

Assume that $T \in G(P)$ is an x-star, and let U(S, T) be a U-clique that includes T. Since T is a star, $S \cup T$ is obtained from T by adding an edge that connects two leaves v, w of T. Hence, the unique cycle of $S \cup T$, ([x, v], [v, w], [w, x]), is of length 3. Thus, $|U(S,T)|=3$, as asserted.

On the other hand, we show that if $T \in G(P)$ is an SST of diameter $\ge 3$, then T belongs to a U-clique of size $\ne 3$. Since $\mathrm {diam}(T) \ge 3$, T contains an internal edge [a, b] (i.e., both a and b are not leaves of T). Consider the graph $T \setminus \{[a,b]\}$, that is obviously a forest with two connected components. Color the vertices of the connected component that includes a black and the vertices of the component that includes b white.

We would like to show that there exists a colorful edge e that uses neither a nor b and does not cross any edge of $T \setminus \{[a,b]\}$ (see Fig. 7). This will conclude the proof, since in such a case, denoting $S = T \cup \{e\} \setminus \{[a,b]\}$, we find that S is an SST, $[S,T] \in G(P)$, and the unique cycle of the graph $S \cup T = T \cup \{e\}$ is of length $\ge 4$. Then, by the geometric interpretation above, if e crosses [a, b] then U(S, T) is a degenerate U-clique, and otherwise, |U(S, T)| is equal to the length of the unique cycle of $S \cup T$, that is $\ge 4$. Hence, in any case, T lies in a U-clique of size $\ne 3$.

Fig. 7

An illustration for the proof of Theorem 3.3—beginning

We extend T to a triangulation ${\mathcal {T}}$ of $\mathrm {conv}(P)$, and consider three cases:

• 1. Case 1: [a, b] is a boundary edge of $\mathrm {conv}(P)$ The edge [a, b], being colorful, is contained in a colorful triangle $\triangle abc \in {\mathcal {T}}$. The other colorful edge of $\triangle abc$ is not a boundary edge of $\mathrm {conv}(P)$, as otherwise, one of the two connected components of $T \setminus \{[a,b]\}$ consists of a single vertex, which contradicts the assumption that [a, b] is an internal edge of T. Denote that colorful edge [a, c]. The neighbors of a in ${\mathcal {T}}$ constitute a path $[b,c,d_1,d_2,\ldots ]$. Since the connected component of a in the graph $T \setminus \{[a,b]\}$ (i.e., the “black” component) includes more than one vertex, at least one of the $d_i$’s is black. Thus, the path contains a colorful edge e that uses neither a nor b (see Fig. 8). Furthermore, as e belongs to ${\mathcal {T}}$, it does not cross any edge of T. Hence, e is the edge whose existence was claimed.

• 2. Case 2: b is an internal vertex of $\mathrm {conv}(P)$ In this case, [a, b] is an internal edge of ${\mathcal {T}}$, and thus, it is contained in two triangles $\triangle abc, \triangle abd \in {\mathcal {T}}$. We further divide this case into two sub-cases:

  • (a) Case 2a: Either c or d (or both) are black Assume w.l.o.g. that c is black. Since b is an internal vertex of $\mathrm {conv}(P)$, the neighbors of b in ${\mathcal {T}}$ constitute a cycle $[d,a,c,d_1,d_2,\ldots ,d_k,d]$. Since the connected component of b in the graph $T \setminus \{[a,b]\}$ contains more than one vertex, at least one of the $d_i$’s or d is white. Since a, c are black, this implies that the cycle includes at least two colorful edges, and at least one of them uses neither a nor b (see left part of Fig. 9). As in Case 1, this is the desired edge e.

  • (b) Case 2b: Both c and d are white By the same argument as above, a has a black neighbor in ${\mathcal {T}}$. As the neighbors of a in ${\mathcal {T}}$ form a (possibly closed) path, at least one edge of this path is colorful (see right part of Fig. 9). This edge uses neither a nor b (as both edges that use b in this path, [b, c] and [b, d], are not colorful). As in the previous cases, this is the desired edge e.

• 3. Case 3: Both a and b are boundary vertices of $\mathrm {conv}(P)$, and [a, b] is a diagonal edge of $\mathrm {conv}(P)$. As in Case 2, [a, b] lies in two triangles $\triangle abc, \triangle abd \in {\mathcal {T}}$. We further divide this case to two sub-cases:

  • (a) Case 3a: c and d are of the same color W.l.o.g., c and d are white. By the same arguments as above, a has a black neighbor, and thus, the path of a’s neighbors includes a colorful edge (see left part of Fig. 10). This edge does not use b, as both edges that use b (that are [b, c], [b, d]) are not colorful, and it clearly does not use a.

  • (b) Case 3b: c and d are of different colors. In this case, the edge [c, d] is as desired, since it is colorful, does not use a, b, and does not cross edges of $T \setminus \{[a,b]\}$ (see right part of Fig. 10). Note that since [c, d] crosses [a, b], the U-clique that includes T in this case is degenerate. This completes the proof of the theorem.$\square$

Fig. 8

An illustration for the proof of Theorem 3.3—Case 1

Fig. 9

An illustration for the proof of Theorem 3.3—Case 2

Fig. 10

An illustration for the proof of Theorem 3.3—Case 3

Remark 3.4

It may happen that $T \in G(P)$ is not a star, but all U-cliques that contain T are either degenerate or of size 3.

3.2 Identification of Brushes in G(P)

Definition 3.5

Let P be a set of points in general position in the plane, and let $p,q \in P$. A pq -brush is an SST of diameter 3 whose only internal edge is [p, q].

Figure 11 shows an example of a pq-brush.

Fig. 11

A pq-brush

In this subsection we aim at identifying the vertices of G(P) that represent brushes. The identification uses distances in the graph G(P), defined (as usual) as the length of the shortest path between two vertices, and denoted by $d_{G(P)}(S,T)$. Note that by the structure of G(P), it is clear that for any pair of vertices $S,T \in G(P)$, we have

$$\begin{aligned} d_{G(P)}(S,T) \ge \tfrac{1}{2} |\Delta (S,T)|, \end{aligned}$$

where $\Delta (S,T)$ is the symmetric difference between the edge sets of the graphs S and T.

Theorem 3.6

An SST $T \in G(P)$ is a pq-brush if and only if it is not a star and

$$\begin{aligned} d_{G(P)} (T,S(p)) + d_{G(P)} (T,S(q)) = n-2. \end{aligned}$$

(1)

For sake of convenience, we divide the theorem into two propositions.

Proposition 3.7

Assume that $T \in G(P)$ satisfies

$$\begin{aligned} d_{G(P)} (T,S(p)) + d_{G(P)} (T,S(q)) = n-2. \end{aligned}$$

Then T is a pq-brush, or $T=S(p)$, or $T=S(q)$.

Proof

First, we note that

$$\begin{aligned} d_{G(P)} (S(p),S(q)) \ge \tfrac{1}{2} |\Delta (S(p),S(q))| = n-2, \end{aligned}$$

and thus, by the triangle inequality,

$$\begin{aligned} d_{G(P)} (T,S(p)) + d_{G(P)} (T,S(q)) \ge n-2 \end{aligned}$$

for any $T \in G(P)$.

Assume that T satisfies (1). Let $k,\ell$ be the numbers of edges of T that emanate from q, p (respectively), and let r be the number of edges of T that use neither p nor q. We consider two cases:

• 1. $[p,q] \not \in T$. In this case, we have

  $$\begin{aligned}&k+\ell +r=n-1, \qquad d_{G(P)} (T,S(p)) \ge \tfrac{1}{2} |\Delta (T,S(p))| = k+r, \qquad \text{ and } \qquad \\&d_{G(P)}(T,S(q)) \ge \tfrac{1}{2} |\Delta (T,S(q))| = \ell +r. \end{aligned}$$

  Hence,

  $$\begin{aligned} d_{G(P)} (T,S(p))+ d_{G(P)} (T,S(q)) \ge k+\ell +2r=(n-1)+r>n-2. \end{aligned}$$

• 2. $[p,q] \in T$. In this case,

  $$\begin{aligned}&k+\ell +r=n, \qquad d_{G(P)} (T,S(p)) \ge \tfrac{1}{2} |\Delta (T,S(p))| = k+r-1, \qquad \text{ and } \qquad \\&D_{G(P)}(T,S(q))| \ge \tfrac{1}{2} |\Delta (T,S(q)) = \ell +r-1. \end{aligned}$$

  Hence,

  $$\begin{aligned} d_{G(P)} (T,S(p))+ d_{G(P)} (T,S(q)) \ge k+\ell +2r-2=n+r-2 \ge n-2, \end{aligned}$$

  and equality can hold only if $r=0$, which means that all edges of T emanate either from p or from q and $[p,q] \in T$, i.e., T is a pq-brush, or $T=S(p)$ or $T=S(q)$.$\square$

Proposition 3.8

Let $T \in G(P)$ be a pq-brush. Then

$$\begin{aligned} d_{G(P)} (T,S(p)) + d_{G(P)} (T,S(q)) = n-2. \end{aligned}$$

In order to prove Proposition 3.8, we need a lemma.

Definition 3.9

Let T be a pq-brush (or $T=S(p)$ or $T=S(q)$). We say that T is of type $(k,\ell )$ if $\mathrm {val}(T,p)=k+1$ and $\mathrm {val}(T,q)=\ell +1$ (i.e., the numbers of edges of T that emanate from p, q are $k+1,\ell +1$, respectively).

Lemma 3.10

If T is a pq-brush (or a star) of type $(k,\ell )$, $k<n-2$, then it is adjacent in G(P) to some pq-brush (or star) $T'$ of type $(k+1,\ell -1)$. (By symmetry, if $\ell <n-2$ then T is adjacent in G(P) to some pq-brush (or star) $T''$ of type $(k-1,\ell +1)$.)

Proof of Lemma 3.10

Assume w.l.o.g. that [p, q] is placed horizontally, and consider the half-plane above it. Let [p, x] be an edge such that the angle $\alpha$ between [p, q] and [p, x] is minimal amongst all edges of T that emanate from p (see Fig. 12). Let $T' = (T \setminus \{[p,x]\}) \cup \{[q,x]\}$. Due to the minimality of the angle $\alpha$, [q, x] does not cross any of the edges of T that emanate from p. Thus, $T'$ is a pq-brush of type $(k+1,\ell -1)$ (or $T'=S(q)$, if $\ell =1$), and $[T,T'] \in G(P)$ since $|\Delta (T,T')|=2$. $\square$

Proof of Proposition 3.8

Let $T \in G(P)$ be a pq-brush. Assume w.l.o.g. that T is of type $(k,\ell )$. Repeated use of Lemma 3.10 enables us to construct a path $\langle T_0,T_1,\ldots ,T_{n-2} \rangle$ in G(P) such that $T_0=S(q)$, $T_{k}=T$, and $T_{n-2}=S(p)$. This implies $d_{G(P)} (T,S(p)) \le \ell$ and $d_{G(P)} (T,S(q)) \le k$, hence, $d_{G(P)} (T,S(p)) + d_{G(P)} (T,S(q)) \le \ell +k=n-2$. Since we have shown above that $d_{G(P)} (T,S(p)) + d_{G(P)} (T,S(q)) \ge n-2$ for any T, this completes the proof. $\square$

Fig. 12

An illustration to the proof of Lemma 3.10

4 Identification of the Geometric Structure of K(P)

In this section we achieve a complete reconstruction of the geometric structure of K(P), based on the identification of stars and brushes presented in Sect. 3. Most of the effort is devoted to obtaining a complete identification of the brushes, in the sense that given a pq-brush T and a vertex $x \ne p,q$, we determine whether $[x,p] \in T$ or $[x,q] \in T$. This step is presented in Sect. 4.1. The finalization of the proof of Theorem 1.3, presented in Sect. 4.2, is easy.

4.1 Further Information on Brushes in G(P)

So far, we know which vertices of G(P) are brushes. Furthermore, if we identify the points of P with the stars in G(P) (an identification that is determined only up to an automorphism of K(P)), we can say for each brush T, what are the vertices p, q that are its “centers”, and how many edges of T emanate from each of the central vertices p, q.

Our goal now is to gain full information on the brushes. Namely, for a pq-brush T and a vertex $x \ne p,q$, we would like to determine whether $[p,x] \in T$ or $[q,x] \in T$.

As an intermediate step, we would like to determine, for given $x,y \ne p,q$, whether both x and y are connected in T to the same vertex (either p or q), or one of them is connected to p and the other to q.

Proposition 4.1

Let T be a pq-brush, and let $x,y \in P$ be different from each other and from p and q. The leaf edges of T whose endpoints are x and y emanate from the same internal vertex of T if and only if for any xy-brush S, we have $d_{G(P)} (T,S) \ge n-2$.

One direction of the proposition is immediate. If the leaf edges emanate from the same vertex, e.g., [p, x], [p, y], then at most one (and actually, exactly one) of these edges can belong to an xy-brush (as ([x, y], [y, p], [p, x]) form a cycle). Since every edge of an xy-brush S emanates from either x or y, we have $\frac{1}{2}|\Delta (S,T)| \ge n-2$ (as these trees have exactly one edge in common). Hence,

$$\begin{aligned} d_{G(P)} (T,S) \ge \tfrac{1}{2}|\Delta (S,T)| = n-2 \end{aligned}$$

for any xy-brush S.

On the other hand, if the leaf edges emanate from different vertices, e.g., [p, x], [q, y], it is possible that an xy-brush S include both these edges, and then $\frac{1}{2} |\Delta (S,T)|=n-3$. We will construct an xy-brush that satisfies this condition, and furthermore, satisfies the stronger condition $d_{G(P)}(S,T)=n-3$. Before we show this construction, we need a few preparations.

Definition 4.2

Let G be a geometric graph, and let O be a point in the plane. We say that O sees a point P if the open segment (O, P) does not meet any edge or vertex of G. We say that O sees an edge $e \in E(G)$ if it sees every point $X \in e$, including the endpoints.

Lemma 4.3

Let $G=(V,E)$ be a crossing-free geometric graph, with no isolated vertices. Suppose V is a disjoint union $V=V_0 \cup W$, where $|V_0|=2$ (say, $V_0=\{p,q\}$), and each edge of G connects a vertex of $V_0$ with a vertex of W. Suppose $O \in \mathbb {R}^2 \setminus \cup \{\mathrm {aff}(e):e \in E(G)\}$. Then O sees some vertex $w \in W$.

We note that a similar lemma was proved in [5]. The assumption on O in [5] is $O \not \in \mathrm {conv}(V(G))$, and the assertion is the same as in our lemma.

Proof

Draw a ray R that emanates from O, crosses some edge of G, and does not meet any vertex of G. (It is clear that such rays exist.) Denote by C the first crossing point of R with an edge of G. Then C is an interior point of an edge, say [p, w], of G, and O sees C. Now rotate R around O towards w, until it hits w. If the triangle $\triangle OCw$ does not contain any vertex of G, except w, then O sees w. Otherwise, there is a first position $R'$ of the rotated ray that meets V. Let v be the point of $R' \cap V$ closest to O. Then O sees v. If $v \in W$, we are done. Assume, therefore, that $v \in V_0$. Clearly, $v \ne p$ since $0< \angle vOp < \angle wOp < \pi$. Hence, $v=q$.

Among the edges that emanate from q, let $[q,w']$ be the edge such that $\angle Oqw'$ is minimal. As before, rotate $R'$ around O towards $w'$, until it hits $w'$. If the triangle $\triangle Oqw'$ does not contain any vertex of G, except q and $w'$, then O sees $w'$. Otherwise, there is a first position $R''$ of the rotated ray that meets V. Let $v'$ be the point of $R'' \cap V$ closest to O. Then O sees $v'$. Now, we observe that $v' \not \in V_0$. Indeed, $v' \ne q$ since $0< \angle v'Oq < \angle qOw' < \pi$, and $v' \ne p$ since $0 < \angle v'Op = \angle v'Oq + \angle qOp < \angle w'Oq + \angle wOp < 2\pi$. Therefore, $v' \in W$, which completes the proof. $\square$

Now we are ready to prove Proposition 4.1.

Proof of Proposition 4.1

We already proved above that if the two leaf edges of T whose endpoints are x, y emanate from the same vertex, then for any xy-brush S, $d_{G(P)} (T,S) \ge n-2$. Assume now that these leaf edges emanate from different vertices. W.l.o.g., these edges are [p, x], [q, y]. We consider two cases, according to the placement of p, q, x, y in the plane. In each case, we show that we can pass from T to a suitable xy-brush S in $n-3$ steps, where in each step we remove one edge and add another edge, while maintaining the simplicity. This will show that $d_{G(P)}(T,S) = n-3$, and thus complete the proof of the proposition. Note that in all the steps of the path connecting T to S, the edges [p, x], [q, y] remain untouched.

Case 1: x, y are on the same side of $\ell (p,q)$.

In this case, at least one of the edges [p, x], [q, y] is included in a line that supports the set $\{p,x,q,y\}$ (which means that all points in the set are on the same side of the line). We assume w.l.o.g. that [p, x] has this property.

Fig. 13

An illustration to the proof of Proposition 4.1: Case 1. The regions are numbered by the order of their consideration, where the missing number 3 corresponds to Phase 3 in which [p, q] is replaced by [x, y]. The notation (i)–(v) where $i \in \{1,2,4\}$ and $v \in \{x,y\}$ means that we are going to connect all points in Region i to v

The passage from T to an appropriate S is performed by a 4-phase procedure, illustrated in Fig. 13. In each phase (except for phase 3 that will be described below), we consider one of the regions of the plane denoted in the figure: 1, 2, 4, and deal with all points of P that belong to that region.

• 1. Region 1 (Reg1) This region is the open half-plane to the left of the line $\ell (p,x)$. Assume that $|P \cap Reg1|=k_1$. We are going to perform $k_1$ steps: in each step, we take one of these points, remove the edge that connects it to either p or q, and add an edge that connects it to x. Of course, we must maintain the simplicity during all steps, and this is achieved using Lemma 4.3.

  Let $G_0$ be the geometric graph whose edges are all edges of T of the form [p, w] or [q, w], where w lies in Reg1. The graph $G_0$ and the point $O=x$ satisfy the assumptions of Lemma 4.3, and thus, by the Lemma, x sees one of its vertices $w \in Reg1$, say $w_1$. Assume, for example, that $[q,w_1] \in E(G_0)$. Define $T_1 = T \setminus \{[q,w_1]\} \cup \{[x,w_1]\}$. Since x sees $w_1$, the edge $[x,w_1]$ does not cross any other edge of T. Thus, $T_1$ is an SST and $|T \triangle T_1|=2$, which implies that $[T,T_1] \in G(P)$.

  Now, we repeat the first step with the SST $T_1$ in place of T. That is, we define $G_1$ whose edges are all edges of T of the form [p, w] or [q, w] where w lies in Reg1, except for $[q,w_1]$. As before, we apply Lemma 4.3 with $G_1$ and $O=x$ and obtain a vertex $w_2$ that is seen from x. Then, we define $T_2$ by removing from $T_1$ the edge that connects $w_2$ to either p or q and adding the edge $[x,w_2]$. Note that the edge $[x,w_1]$ that was not included in $G_2$ cannot cross $[x,w_2]$, as they both emanate from x.

  By continuing in the same fashion, we obtain a sequence $T_0,T_1,\ldots ,T_{k_1}$ such that $T_0=T$, $[T_i,T_{i+1}] \in G(P)$ for all i, and in $T_{k_1}$, all points in $P \cap Reg1$ are connected to x.

  It should be noted that the parts of $T_i$ that are not included in the auxiliary graph $G_i$, i.e., the edge [p, q] and the edges [p, w], [q, w], $w \in \mathbb {R}^2 \setminus Reg1$, are all disjoint from the convex set Reg1, and thus cannot cross the new edge $[x,w_{i+1}]$ (as $x \in \mathrm {bdry}(Reg1)$).

• 2. Region 2 (Reg2) This region contains all points that lie above $\ell (p,q)$ and on the right side of $\ell (p,x)$. Assume that $|P \cap Reg2|=k_2$. We start with $T_{k_1}$ and perform $k_2$ steps: in each step, we consider one of these points, remove the edge that connects it to either p or q, and add an edge that connects it to y. As before, the simplicity is maintained during all steps, by using Lemma 4.3.

  Let $G_{k_1}$ be the geometric graph whose edges are all edges of $T_{k_1}$ of the form [p, w] or [q, w], where w lies in Reg2. The graph $G_{k_1}$ and the point $O=y$ satisfy the assumptions of Lemma 4.3, and thus, by the Lemma, y sees one of the vertices $w \in Reg2$, call it $w_{k_1+1}$. Without loss of generality, $[p,w_{k_1+1}] \in G_{k_1}$. Define $T_{k_1+1} = T_{k_1} \setminus \{[p,w_{k_1+1}]\} \cup \{[y,w_{k_1+1}]\}$. Since y sees $w_{k_1+1}$, the edge $[y,w_{k_1+1}]$ does not cross any other edge of $T_{k_1}$. Thus, $[T_{k_1},T_{k_1+1}] \in G(P)$.

  By continuing in the same fashion, we obtain a sequence $T_{k_1+1},T_{k_1+2},\ldots ,T_{k_1+k_2}$ such that $[T_i,T_{i+1}] \in G(P)$ for all i, and in $T_{k_1+k_2}$, all points in $P \cap Reg1$ are connected to x and all points in $P \cap Reg2$ are connected to y.

• 3. Phase 3 In this phase, we add the edge [x, y] and remove the edge [p, q] (that otherwise closes a cycle ([x, y], [y, q], [q, p], [p, x])). Formally, we define $T_{k_1+k_2+1} = T_{k_1+k_2} \setminus \{[p,q]\} \cup \{[x,y]\}$. Note that the edge [x, y] does not cross any edge of $T_{k_1+k_2}$, as in $T_{k_1+k_2}$, all points of $P \cap Reg2$ are connected to y.

• 4. Region 4 (Reg4) This region contains all points that lie below $\ell (p,q)$ and on the right of $\ell (p,x)$. Assume $|P \cap Reg4|=k_3$. As all points of P except for p, q, x, y belong to one of the regions: Reg1, Reg2, Reg4, we have $k_1+k_2+k_3=n-4$. We construct a sequence of SSTs $T_{k_1+k_2+2},\ldots ,T_{k_1+k_2+k_3+1}$ such that in $T_{k_1+k_2+k_3+1}$, all points in $P \cap Reg1$ are connected to x and all points in $P \cap (Reg2 \cup Reg4)$ are connected to y. Hence, $T_{k_1+k_2+k_3+1}=T_{n-3}$ is an xy-brush that satisfies $d_{G(P)} (T,T_{n-3}) = n-3$, as desired.

  Let $G_{k_1+k_2+1}$ be the geometric graph whose edges are all edges of $T_{k_1+k_2+1}$ of the form [p, w] or [q, w], where w lies in Reg4. The graph $G_{k_1+k_2+1}$ and the point $O=y$ satisfy the assumptions of Lemma 4.3, and thus, by the Lemma, y sees one of the vertices $w \in Reg4$, say $w_{k_1+k_2+1}$. Without loss of generality, $[p,w_{k_1+k_2+1}] \in G_{k_1+k_2+1}$. Define $T_{k_1+k_2+2} = T_{k_1+k_2+1} \setminus \{[p,w_{k_1+k_2+1}]\} \cup \{[y,w_{k_1+k_2+1}]\}$. Since y sees $w_{k_1+k_2+1}$, the edge $[y,w_{k_1+k_2+1}]$ does not cross any other edge of $T_{k_1}$. (It should be noted that the fact that y lies outside Reg4 does not disturb us, as all points in Region 2 (that is the region y sees Reg4 through) are already connected to y, and P is in general position.) Thus, $[T_{k_1+k_2+1},T_{k_1+k_2+2}] \in G(P)$.

  By continuing in the same fashion, we obtain a sequence $T_{k_1+k_2+2},T_{k_1+k_2+3},\ldots ,T_{k_1+k_2+k_3+1}$ such that $[T_i,T_{i+1}] \in G(P)$ and $T_{k_1+k_2+k_3+1}=T_{n-3}$ is the desired xy-brush.

Case 2: x, y are on different sides of $\ell (p,q)$.

This case is treated in a fashion similar to Case 1. We divide all points of $P \setminus \{p,q\}$ into two regions, where Region 1 (Reg1) consists of the points above $\ell (p,q)$ and Region 2 (Reg2) consists of the points below $\ell (p,q)$ (see Fig. 14). In the first phase, we consider the points of Reg1 (excluding x), disconnect them from p or q and connect them to x instead. The procedure is identical to the procedure of the first phase of Case 1. In the second phase, we consider the points of Reg2 (excluding y), disconnect them from p or q and connect them to y instead. The procedure is, again, similar. Finally, in the third phase we remove the edge [p, q] and insert the edge [x, y] instead. (As at this stage, all points in $P \setminus \{p,q,x,y\}$ are connected to either x or y, this step does not create crossings.) As a result, we obtain a sequence $T=T_0,T_1,T_2,\ldots ,T_{n-3}$, such that $[T_i,T_{i+1}] \in G(P)$ for all i and $T_{n-3}$ is an xy-brush, as desired.

As cases 1, 2 include all possible placements of x, y, p, q, the proof is complete. $\square$

Fig. 14

An illustration to the proof of Proposition 4.1: Case 2. The notation $(i) - (v)$ where $i \in \{1,2\}$ and $v \in \{x,y\}$ means that the points in Region i are connected to v

Now we are ready to identify every brush completely.

Corollary 4.4

Let $T \in V(G(P))$ be a pq-brush and let $x \in P$, $x \ne p,q$. Given G(P), we can determine whether $[p,x] \in T$ or $[q,x] \in T$.

Proof

It follows from the proof of Proposition 3.8 that T belongs to a path

$$\begin{aligned} \langle S(p)=T_0, T_1, T_2,\ldots ,T_{n-3},T_{n-2}=S(q) \rangle \end{aligned}$$

in G(P) such that in $T_i$, $\deg (p)=n-1-i$ and $\deg (q)=i+1$. Consider $T_1$. Since it has only one vertex $x_1 \ne p,q$ that is connected to q, we can use Proposition 4.1 to determine it. (Here we use the assumption that $n \ge 5$.) We can then move to $T_2$ and use Proposition 4.1 again to determine the additional vertex $x_2$ connected to q in $T_2$. (Note that $[x_1,q] \in E(T_2)$, and thus, $x_2$ is identified as the unique vertex x such that the leaf edge of $T_2$ that emanates from it has the same second endpoint as the leaf edge that emanates from $x_1$.) We can continue in the same fashion and get a complete identification of $T_1,T_2,\ldots ,T_{n-3}$, including T. $\square$

4.2 Completing the Proof of Theorem 1.3

Our last step toward the identification of the geometric structure of K(P) is the following easy proposition.

Proposition 4.5

Let p, q, x, y be four different points in P. The segments [p, x] and [q, y] do not cross if and only if there exists a pq-brush that includes the edges [p, x] and [q, y].

Proof

It is clear that if [p, x] and [q, y] cross then no pq-brush can contain both edges [p, x] and [q, y], as a brush is a simple tree. If [p, x] and [q, y] do not cross, then they are strictly separated by some line $\ell$. In such a case, we can define a pq-brush in which all vertices that lie on the same side of $\ell$ as p are connected to p, and all other vertices are connected to q (see Fig. 15). This pq-brush includes both [p, x] and [q, y]. $\square$

Now we are ready to prove our main theorem.

Proof of the main theorem

Consider the geometric tree graph G(P). The vertices x, y, p, q are identified with the stars $S(x),S(y),S(p),S(q) \in G(P)$. By Theorem 3.6, we can identify all pq-brushes in G(P). By Corollary 4.4, we can check for each of them whether it includes both [p, x] and [q, y] or not. By Proposition 4.5, if none of the pq-brushes contains both [p, x] and [q, y], then these segments cross, and otherwise, they do not cross. This completes the proof of the theorem. $\square$

Fig. 15

An illustration to the proof of Proposition 4.5

5 The Automorphism Group of the Tree Graph of $K_n$

In this section we consider the abstract (i.e., non-geometric) graph $K_n$. Recall that, as defined in the introduction, the vertices of the tree graph $G(K_n)$ are all the spanning trees of $K_n$, and two spanning trees are adjacent if they differ in exactly two edges. We prove Theorem 1.4, stating that the automorphism group of $G(K_n)$ is isomorphic to $\mathrm {Aut}(K_n)=S_n$.

It turns out that the theorem can be proved by roughly the same methodology as the proof of Theorem 1.3, as shown below. Altogether, the proof in the abstract setting turns out considerably simpler than its geometric counterpart.

Identification of stars in $G(K_n)$. Denote $G=G(K_n)$, and let $V(K_n)=\{v_1,\ldots ,v_n\}$. As in the geometric case, our first step is identification of the vertices of G that represent stars. Unlike the geometric case, here the identification is immediate.

Claim 5.1

Let $T \in V(G)$. Then T represents a star if and only if for any $T' \in V(G)$, $d_G(T,T') \le n-2$.

Proof

We observe that in the abstract case, $d_G(S_1,S_2) = \frac{1}{2} |\Delta (S_1,S_2)|$ for any $S_1,S_2 \in V(G)$. (In the geometric case, we could only say that $d_{G(P)}(S_1,S_2) \ge \frac{1}{2} |\Delta (S_1,S_2)|$.)

Assume that T is a star. Since any spanning tree $T'$ of $K_n$ shares at least one edge with T, we have $d_G(T,T') = \frac{1}{2} |\Delta (T,T')| \le n-2$.

On the other hand, if T is not a star then it is easy to see that the graph $T^c = K_n \setminus T$ is connected, and thus, there exists $T' \in V(G)$ that does not share an edge with T. Hence, $d_G(T,T') = \frac{1}{2} |\Delta (T,T')| = n-1$. $\square$

We note that since the distance in G between any pair of stars in $n-2$, it follows that the quantity $\max _{\{T' \in V(G): T'\ne T\}} d_G(T,T')$ equals $n-2$ if T represents a star and $n-1$ otherwise. Consequently, the set of vertices that represent stars is exactly the center of the graph G.

These vertices can be identified with the vertices of $K_n$ in an arbitrary way (as any automorphism of $K_n$ clearly induces an automorphism of G). So, we call the n vertices in G that represent stars $S(v_1),\ldots ,S(v_n)$ (in some arbitrary order).

Valences of vertices in $G(K_n)$. The next simple step is identifying, for any $T \in V(G)$ and any vertex v, what is the valence of v in T. Note that we were not able to obtain such an identification in the geometric setting.

Claim 5.2

Let $T \in V(G)$ and $v \in V(K_n)$. The valence $\delta _T(v)$ of v in T is $n-1-d_G(T,S(v))$.

Proof

Since all edges in S(v) emanate from v, it is clear that $\frac{1}{2} |\Delta (T,S(v))| = n-1-\delta _T(v)$. As $d_G(T,S(v)) = \frac{1}{2} |\Delta (T,S(v))|$, the assertion follows. $\square$

Max-cliques in $G(K_n)$. Our next step is examination of max-cliques in G. As in the geometric case, we would like to determine whether a given max-clique is a U-clique or an I-clique.

Proposition 5.3

Given a max-clique $\mathcal {C}$ of G, we can determine whether it is a U-clique or an I-clique.

Proof

As the discussion in Sect. 2.2 is purely combinatorial, it applies without change to the abstract setting. In particular, all vertices in a U-clique U(S, T) are obtained from $S \cup T$ by removing an edge from its unique cycle, and all vertices in an I-clique I(S, T) are obtained from the two-component forest $S \cap T$ by adding an edge that connects its two components. As there are no geometric restrictions in our case, it follows that |U(S, T)| is equal to the size of the unique cycle in $S \cup T$ (and, in particular, is between 3 and n), and $|I(S,T)|=k(n-k)$, where k is the number of vertices in one of the connected components of $S \cap T$. Hence, determination whether $\mathcal {C}$ is a U-clique or an I-clique is non-trivial only if $|\mathcal {C}|=n-1$.

A U-clique U(S, T) is of size $n-1$ if the unique cycle C of $S \cup T$ is of size $n-1$, which means that $S \cup T$ consists of C plus a single additional edge. Each element of U(S, T) is obtained from $S \cup T$ by removing one edge from C. Assume w.l.o.g. that $C= \langle v_1,v_2,\ldots ,v_{n-1},v_1 \rangle$, and the additional edge is $[v_n,v_1]$. It is clear that $v_1$ is never a leaf in a tree of U(S, T), $v_n$ is a leaf in all $n-1$ trees of U(S, T), and each of the vertices $v_2,\ldots ,v_{n-1}$ is a leaf in exactly two trees of U(S, T). In addition, U(S, T) has two trees that are paths. (These are the trees obtained by removing $[v_1,v_2]$ and $[v_{n-1},v_1]$.) These two trees can be recognized by checking that their sequence of valences is $1,2,2,\ldots ,2,1$.

An I-clique I(S, T) is of size $n-1$ if in the two-component forest $S \cap T$, one component consists of a single vertex x. Assume, in addition, that I(S, T) has two elements that are paths. (Otherwise, we can determine that I(S, T) is an I-clique by the previous paragraph.) This is possible only if the second component of $S \cap T$ is a path P. In such a case, each endpoint of P is a leaf in $n-2$ (of the $n-1$) trees of I(S, T). As in U(S, T), all vertices except one are leaves in at most two trees of U(S, T), this property allows to determine that I(S, T) is indeed an I-clique. $\square$

The automorphism group of $G(K_n)$. Our last step is to show that the information on G obtained so far is sufficient for determining uniquely the spanning tree represented by each vertex of G. Namely, given $T \in V(G)$ and two vertices $p,q \in V(K_n)$, we would like to determine whether $[p,q] \in E(T)$ or not. If this is possible, it implies that $\mathrm {Aut}(G) \cong \mathrm {Aut}(K_n) \cong S_n$, since our determination is unique up to the arbitrary identification of the vertices of G that represent stars with the vertices of $K_n$. Hence, this will complete the proof of Theorem 1.4.

First, we consider the case when neither p nor q is a leaf in T.

Claim 5.4

Let $T \in V(G)$ and suppose $p,q \in V(K_n)$, $p \ne q$, $\delta _T(p),\delta _T(q) \ge 2$. Then $[p,q] \in E(T)$ if and only if T has a neighbor $T'$ in G in which the valences of both p and q are smaller by 1 than in T.

Proof

If $[p,q] \not \in E(T)$ then no removal of an edge from E(T) can reduce the valences of both p and q, and thus, $T'$ as described in the claim does not exist. On the other hand, if $[p,q] \in E(T)$ then the graph $\tilde{T} = T \setminus \{[p,q]\}$ is a two-component forest in which both components are of size $\ge 2$. Hence, there exists an edge $[p',q']$ that connects the two components of $\tilde{T}$ and uses neither p nor q. The tree $T' = T \setminus \{[p,q]\} \cup \{[p',q']\}$ is a neighbor of T as described in the claim. $\square$

Now we can assume w.l.o.g. that p is a leaf in T. We perform a four-step procedure:

• 1. Find a leaf $p'$ of T such that $d_T(p,p') >2$.

• 2. Find a neighbor $T'$ of T in $G(K_n)$ such that $\delta _{T'}(p),\delta _{T'}(p') \ge 2$.

• 3. Consider the U-clique $U(T,T')$, and find a tree $S \in U(T,T')$ such that $\delta _S(p)=1$ and $\delta _S(p')=2$.

• 4. We find a vertex $p''$ such that $\delta _S(p'') = \delta _T(p'')-1$. We claim that if $p''=q$ then $[p,q] \in E(T)$, and otherwise, $[p,q] \not \in E(T)$.

We show below that the four steps can indeed be performed, and that they allow to determine whether $[p,q] \in E(T)$ or not, as claimed.

Step 1 First, we note that if $d_T(p,p')=2$ for all leaves $p'$ of T, then T is a star, and thus, $[p,q] \in E(T)$ for the unique q whose valence in T is greater than 1 and $[p,q] \not \in E(T)$ for any other q. Hence, we may assume that there exists a leaf $p'$ such that $d_T(p,p')>2$, and we only have to detect it.

Consider the set of leaves of T other than p: $A = \{p_i \in V(K_n): p_i \ne p, \delta _T(p_i)=1\}$. (Note that we can recognize this set, as we are able to determine valences of vertices.) We claim that $d_T(p,p') > 2$ if and only if there exists a neighbor $T'$ of T in $G(K_n)$ such that $\delta _{T'}(p)=\delta _{T'}(p')=2$. This allows to detect the desired $p'$ by going over the elements of A, and for each of them, going over the neighbors of T in $G(K_n)$ and checking whether the claimed neighbor exists.

To see that the claim holds, note that a neighbor $T'$ of T satisfies $\delta _{T'}(p)=\delta _{T'}(p')=2$, if and only if it is of the form $T' = T \setminus \cup \{[p,p']\} \setminus \{e\}$, for an edge e that belongs to the unique cycle C of $T \cup \{[p,p']\}$ and uses neither p nor $p'$. If $d(p,p')=2$, then C is of length 3, and thus, it has no edges that use neither p nor $p'$. Thus, no such neighbor $T'$ exists. If $d(p,p')>2$, then C is of length $>3$, and thus, it includes an edge e that uses neither p nor $p'$. The tree $T' = T \setminus \{e\} \cup \{[p,p']\}$ is the desired neighbor of T.

Step 2 This step is immediate, as the required neighbor $T'$ was already found in Step 1.

Step 3 The required neighbor S is the tree obtained from $T \cup \{[p,p']\}$ by removing the unique edge of the cycle C that uses p but not $p'$ (call it $[p,p'']$). The U-clique $U(T,T')$ can be recognized using Proposition 5.3, since there exist only two max-cliques of $G(K_n)$ that include both T and $T'$—a U-clique and an I-clique—and Proposition 5.3 allows us to determine, which of them is the U-clique. Then, S can be recognized as the unique element of $U(T,T')$ in which the valences of $p,p'$ are 1 and 2, respectively.

Step 4 It is clear that the unique vertex whose valence in S is smaller by one than its valence in T is $p''$, as defined in Step 3. By the construction of C, $[p,p'']$ is the unique edge of E(T) that emanates from p, i.e., $p''$ is the unique neighbor of p in T. Hence, $[p,q] \in E(T)$ if and only if $q=p$”, as asserted. The vertex p” is detected by comparing the valences of the vertices in S with their respective valences in T.

This completes the proof of Theorem 1.4.