Is adjacency of vertices also independent of the representation used? Conversely, is it possible that, given two vertices $u$ and $v$, they are adjacent under one representation, but not adjacent under a different representation?
You asked about vertices. A vertex is a basic feasible solution, which is more specific than merely a basic solution. Adjacency of vertices/bfs's is a geometric property of polyhedra; as such, it is independent of the representation used. Here's a proof.
If $x$ and $y$ are two distinct vertices, of the polyhedron $P = \{z \in \mathbb{R}^n\mid: a'_i z \leq b_i, i \in \{1, \dots, m\}\}$, there are $n - 1$ independent constraints that are active at both $x$ and $y$, say the first $n - 1$ constraints. Then $\Delta := \{a_i'\cdot z \leq b_i,\ i \in 1, \dots, n - 1\}$ is a subsystem of full rank (i.e. $a_1, \dots, a_{n - 1}$ are independent) and $x$ and $y$ are solutions to this subsystem. According to Proposition 3.3.2 of [2] (p. 46) (which is proved there):
Let $P = \{x \in \mathbb{R}^n\mid a^i\cdot x = b^i, i = 1, \dots, m\}$ be a polyhedral convex set. If the system $a^i\cdot x = b^i$, $i = 1, \dots, m$ has a subsystem of rank $n - 1$, let $\Delta$ be the line of the solutions to this subsystem. Then either $P \cap \Delta$ has at most one point, or $P \cap \Delta$ is a $1$-dimensional face of $P$. Conversely, every line which contains a $1$-dimensional face of $P$ is the solution to such a subsystem.
Where a face of the convex set $A$ is defined ([2] p. 37) to be
a convex subset $F$ of $A$ verifying:
$$
\left.\begin{aligned}
x & \in F \cap (y,z) \\
y & \in A, z \in A
\end{aligned}\right\} \implies y \in F, z \in F
$$
Hence $F := P \cap \Delta$ lies along the line that passes through $x$ and $y$, and for every $a, b \in P$, if $\lambda a + (1 - \lambda) b \in F$ for some $\lambda \in (0,1)$, $a, b \in F$.
If $Q = \{\alpha^i\cdot x \leq \beta^i, i = 1, \dots, \ell\}$ is any other representation of $P$, $x$ and $y$ are still vertices of $Q$ and we still have that $F$ is a convex subset of $Q$ that lies along the line that passes through $x$ and $y$ and for every $a, b \in Q$, if $\lambda a + (1 - \lambda) b \in F$ for some $\lambda \in (0,1)$, $a, b \in Q$. Hence the line through $x$ and $y$ contains a $1$-dimensional face of $Q$ (namely, $F$) and is thus a solution to a subsystem $\Delta'$ of $n - 1$ independent constraints $\{\alpha'_1\cdot z = \beta_1, \cdots, \alpha'_{n - 1}\cdot z = \beta_{n - 1}\}$ of $Q$. In particular, $Q$'s first $n - 1$ constraints are independent and active at $x$ and at $y$, which means that $x$ and $y$ are adjacent vertices of $Q$ as per Bertsimas & Tsitsiklis.
Your intuition is correct. If the polyhedron is identical with the line segment between $x$ and $y$, the result is immediate. Otherwise, a proof can be obtained using Proposition 3.2.6 of [2], p. 45 (which is proved there):
Let $P$ and $C$ be nonempty convex sets such that $P$ is polyhedral and $P \cap \mbox{ri}(C) = \emptyset$. Then there exists a hyperplane separating $P$ and $C$ which does not contain $C$.
Here $\mbox{ri}\, (A)$ is the relative interior of the convex set $A \subset \mathbb{R}^n$, defined ([2], p. 12) as
the set of the points $x$ of $A$ such that there exists a ball with center $x$ and radius $\varepsilon$ whose intersection with $\mbox{aff}\, A$ is contained in A
and $\mbox{aff}\, A$ is the affine hull of $A$, characterized (Proposition 1.1.3, p. 3) as being
the set of all affine combinations of finitely many members of $A$
where an affine combination of $\{x^1, \dots, x^p\}$ is ([2], p. 3) any vector of the form $\sum_{k = 1}^p\lambda_k x^k$ such that $\sum_{k = 1}^p\lambda_k = 1$.
Here's how you do it. Apply Proposition 3.2.6 cited above, setting $P$ to be the face comprising the line segment connecting $x$ and $y$ and setting $C$ to be the given polyhedron of which $x$ and $y$ are adjacent vertices. To see that $P \cap \mbox{ri}(C) = \emptyset$, let $p \in P$. Suppose to the contrary that $p \in \mbox{ri}(C)$ and let $\varepsilon \in (0,\infty)$ be such that whenever $r \in \mbox{aff}\, C$ satisfies $\|r - p\| < \varepsilon$, $r \in C$. Let $q \in C\setminus P$ (recall that we are assuming that $C\setminus P \neq \emptyset$). Let $q' := \lambda p + (1 - \lambda)q$ for some $\lambda > 1$ such that $\|q' - p\| < \varepsilon$. Then, by the choice of $\varepsilon$, $q' \in C$. But then $p$ can be expressed as a convex combination of $q$ and $q'$, so we must have $q, q' \in P$ (since P is a face of $C$), in contradiction to how we chose $q$.
I will prove a weaker result, where "basic solution" is replaced with "basic feasible solution" and where "base" is replaced with "feasible base" (a base $B$ is feasible iff $B^{-1}b \geq 0$). Additionally, I will use part 1 to replace "adjacent basic feasible solutions" with "adjacent vertices". So, to sum up, I will prove the following theorem:
Considering a polyhedron in standard form,
Adjacent vertices (in the sense that the line segment between them is a 1-dimensional face of the polyhedron) can always be expressed as bfs's corresponding to adjacent feasible bases.
Conversely, if two adjacent feasible bases lead to two distinct bfs's, then the latter are adjacent vertices (in the sense specified above).
Part 2 is proved in Proposition 8.13 of [1] (p. 221):
(algebraic characterization of adjacency) Let $\mathbf{u}$ and $\mathbf{v}$ be the extreme points that correspond to the partitions $(\mathbf{B}^1, \mathbf{N}^1)$ and $(\mathbf{B}^2, \mathbf{N}^2)$ described above. Then $\mathbf{u}$ and $\mathbf{v}$ are adjacent BFSs.
which, "translated" to Bertsimas and Tsitsiklis's vocabulary would read:
Let $\mathbf{u} = (\mathbf{B}_1^{-1}\mathbf{b}, \mathbf{0})$ and $\mathbf{v} = (\mathbf{B}_2^{-1}\mathbf{b}, \mathbf{0})$ be two distinct bfs's of a polyhedron given in standard form. Then $\mathbf{u}$ and $\mathbf{v}$ are adjacent vertices (i.e. the line segments connecting the two vertices is a 1-dimensional face of the feasible set).
Whereas part 1 is proved by the implication $\mbox{(b)}\implies\mbox{(c)}$ of theorem 2.10 of [3], p. 61:
Let $P$ be a polytope, $F = \{x: Ax = b, x\geq 0\}$ the corresponding feasible set, and $\hat{x} = (x_1, \dots, x_{n - m})$, $\hat{y} = (y_1, \dots, y_{n - m})$ be distinct vertices of $P$. Then the following are equivalent.
(a) The segment $[\hat{x}, \hat{y}]$ is an edge of $P$.
(b) For every $\hat{z} \in [\hat{x}, \hat{y}]$, if $\hat{z} = \lambda \hat{z}' + (1 - \lambda) \hat{z}''$ with $0 < \lambda < 1$ and $\hat{z}', \hat{z}'' \in P$, then $\hat{z}', \hat{z}'' \in [\hat{x}, \hat{y}]$.
(c) The corresponding vectors $x$, $y$ of $F$ are adjacent bfs's.
which, "translated" to Bertsimas and Tsitsiklis's vocabulary would read (I have "translated" only the relevant implication):
Let $F = \{x: Ax = b, x\geq 0\} $ be a polyhedron given in standard form, and let $\hat{x}$, $\hat{y}$ be distinct vertices of $F$. Then if $\hat{x}$ and $\hat{y}$ are adjacent vertices (in the sense that the line segments connecting them is a face of dimension 1, then they can be expressed as the bfs's $\hat{x} = (B_1^{-1}b\ 0)$ and $\hat{y} = (B_2^{-1}b\ 0)$, where $B_1$ and $B_2$ are two adjacent feasible bases.
(As a matter of fact, part 2 can also be obtained from [3]'s theorem 2.10, but I find [3]'s proof of this direction far less clear than the proof in [1]).
Best Answer
Hint:
Consider the feasible region of this graph:
Then, consider the objective function of the model (the green line) on this feasible region:
Then, consider this in three dimensions:
Where the optimal region is a triangle with each optimal solution $x^*$ having two adjacent $x^{**}$ and $x^{***}$.
Then, in a fourth dimension, there would exists four equally optimal points and so on with higher dimensions. Think about how the Simplex method would handle these, and how this works intuitively with the objective function.
With each additional dimension we add, we're going from a line, to a triangle, to a tetrahedron, and so on.
In other words, a one simplex, a two simplex, a three simplex, a four simplex, and so on.