A counterexample to Question 9.2 in the 2014 topology problem list

Working note, 18 September 2026.

Mathematical status: complete elementary argument for the question as printed. Literature status: priority and novelty have not been established. This note does not assert that the question remained open until 2026. No external specialist review or formal proof-assistant verification is claimed.

Source and exact question

T. Ohtsuki, editor, Problems on Low-dimensional Topology, 2014, Section 9, contribution by Takahiro Matsushita, Question 9.2, pp. 13-14. The supplied file is prob14.pdf.

The source defines the open neighborhood by

$$N(v)=\{w:(v,w)\in E(G)\}.$$

It asks whether a connected graph must be finite if its degrees are uniformly bounded and, for every pair of distinct vertices $v,w$,

$$N(v)\ne N(w),\qquad |N(v)\cap N(w)|\ne1.$$

The answer is no. The construction below is a simple undirected graph, so it does not rely on allowing loops or multiple edges.

Construction

Put

$$V(G)=\mathbb Z\times\{0,1\}.$$

Join the two vertices in each column $\{i\}\times\{0,1\}$. Join every vertex of column $i$ to both vertices of columns $i-1$ and $i+1$. There are no other edges.

Equivalently, $G$ is the lexicographic product of the doubly infinite path with $K_2$. Its neighborhoods are

$$N(i,a)=\{(i,1-a)\}\cup\bigl(\{i-1,i+1\}\times\{0,1\}\bigr).$$

Proof

There are infinitely many columns. Consecutive columns are joined, and each column is connected, so $G$ is infinite and connected.

The displayed neighborhood contains exactly five vertices. Hence $G$ is 5-regular and its degrees are uniformly bounded.

For distinct $v=(i,a)$, $w=(j,b)$, put $d=|i-j|$.

To check the last case, all neighbors of a vertex in column $i$ lie in columns $i-1,i,i+1$, and for $d\ge3$ the corresponding column sets do not overlap. The other cases follow immediately by intersecting the two displayed neighborhoods.

Thus the common-neighbor count is never one. Moreover, every neighborhood has size five, whereas the intersection of two distinct vertices’ neighborhoods has size at most four. Equal neighborhoods are therefore impossible.

Every hypothesis of Question 9.2 holds, but $G$ is infinite. This proves the negative answer. $\square$

Strengthening: the counterexample can be bipartite

Define $B$ with vertex set

$$V(B)=V(G)\times\{0,1\}$$

and edges $(v,\epsilon)\sim(w,1-\epsilon)$ exactly when $v\sim w$ in $G$. Then

$$N_B(v,\epsilon)=N_G(v)\times\{1-\epsilon\}.$$

This graph is bipartite and 5-regular. Vertices in opposite parts have disjoint neighborhoods. Distinct vertices in the same part have the same common-neighbor counts as their distinct base vertices in $G$, namely zero, two, or four. Hence all open neighborhoods are distinct and no pair has exactly one common neighbor.

The double cover is connected. Indeed, $(0,0),(0,1),(1,0)$ form a triangle in $G$. Lifting that triangle gives a path from $((0,0),0)$ to $((0,0),1)$. Any path in the connected base graph can then be lifted starting in either parity, reaching either lift of any base vertex.

Even all closed neighborhoods in $B$ are distinct. For vertices in the same part, the intersection of each closed neighborhood with that part is its own singleton, so two such neighborhoods cannot agree. For vertices in opposite parts, a closed neighborhood has one vertex in its own part and five in the other, so the partwise cardinalities prevent equality.

Consequently, forbidding triangles or requiring both open and closed neighborhoods to distinguish vertices does not restore the proposed finiteness statement.

Computation and its scope

check_question_9_2.py uses only the Python standard library. It constructs exact neighborhoods in the infinite graph, without truncating or wrapping the graph. It checks 1,225 pairs of selected base vertices and 4,950 pairs in the bipartite double cover. All checks passed. The output is verification.json.

These checks corroborate the arithmetic. The proof above, not the finite test window, establishes the claim for every pair of integer positions.

Significance and next validation

This is a direct resolution of one explicitly numbered question in the supplied document, rather than merely a computational observation or a proposed research approach. Its argument is elementary; the fact that a question appeared in a 2014 open-problem list is not evidence that this construction is a new 2026 result.

The remaining verification is bibliographic and communicative: determine whether the question was subsequently answered or whether its author intended a stronger hypothesis not present in the printed statement. The bipartite strengthening rules out two natural attempts to explain the example away. No public priority claim is justified by the present literature search.