Consider the complete bipartite graph $K_{n,n}$ on $2n$ vertices (e.g. there are vertices $v_1,\dots,v_{2n}$ with an edge between $v_i$ and $v_j$ iff $i\not\equiv j \pmod{2}$).
A complete labelling is a way of assigning to each edge in $K_{n,n}$ a distinct (unordered) pair of integers $\{p,q\}$ where $1 \leq p,q \leq 2n$, such that for each vertex the labels of edges incident to it include each of the integers from $1$ to $2n$. Loosely, each vertex can 'see' every number in its adjoining edges.
Question: For which $n$ does a complete labelling exist?
Observations: It's vacuously possible for $n=1$ and impossible for $n=2$ as quickly one can see we are required to repeat a label. Since the number of possible labels is ${2n\choose 2}= 2n^2-n$ and there are $n^2$ edges, it's possible there'll always be 'enough' labels to reliably obtain a complete labelling. There are some 'obvious' implicit rules or alternative interpretations:
- Each integer must appear exactly $n$ times across all labels.
- Grouping vertices by 'connected to an edge labelled with $k$' partitions the vertices into disjoint pairs.
- After some permutation of the numbers $1,\dots,2n$, one vertex must have incident edges with labels $\{1,2\},\{3,4\},\dots,\{2n-1,2n\}$.
Investigations: A little pen-and-paper tinkering found me a solution for $n=3$, and some (not terribly sophisticated) python code generated solutions for $n\leq 7$ using a Wave Function Collapse algorithm. It failed to find a solution for $n=8$ after $50000$ attempts - though I am unsure if this represents a lower likelihood of a 'guess' solution being correct given the greater computation required. A solution for $n=5$ is shown below.
Conjecture: A complete labelling exists for all natural numbers $n\neq 2$. Although, I neither a strong logical or evidential basis for this, so I await disproval excitedly!
I attempted an inductive argument, though it seemed fruitless given that while $K_{n+1, n+1}$ contains copies of $K_{n,n}$ as subgraphs, their corresponding sub-labellings clearly cannot be complete. Perhaps with some suitable exchanges it is possible to find a labelling for $n+1$ given $n$, but I attempted to find a pen-and-paper solutions for $n=4$ from a solution for $n=3$ to no avail. It might also help to consider how many complete labellings a given graph might be expected to have.
One other approach I have considered but not investigated thoroughly is potentially establishing the notion of a 'dual' graph (not in the usual sense of planar graphs) whose vertices correspond to edges in $K_{n,n}$ in some way, then potentially results from the theory of vertex-colouring might provide an answer.
We can think of edges of $K_{n,n}$ as cells in an $n \times n$ grid: the vertices on one side of $K_{n,n}$ are the rows, the vertices on the other side are the columns, and cell $(i,j)$ corresponds to the edge between row-vertex $i$ and column-vertex $j$. In this interpretation, we want to label the cells by distinct pairs $\{p,q\}$ such that every row and every column contains every number exactly once.
Suppose we add an additional constraint: every pair must have one element from $\{1,2,\dots,n\}$ and one element from $\{n+1,n+2,\dots,2n\}$. (This seems just barely possible: this gives $n^2$ possible pairs, which is exactly how many we need.) Then we can separate out the "small" elements and "large" elements into two $n \times n$ grids. Each grid is a Latin square; the requirement that our pairs $\{p,q\}$ should be distinct turns into a requirement that the two Latin squares are orthogonal.
Pairs of orthogonal Latin squares are also called Graeco-Latin squares, and are known to exist for every $n>2$ except for $n=6$. This gives us a solution to the problem in this question for every $n>2$ except for $n=6$, as well. For example, we can turn Wikipedia's example of an order-$5$ pair of orthogonal Latin squares into the $5 \times 5$ grid
\begin{array}{ccccc} \{1,6\} & \{2,9\} & \{3,7\} & \{4,10\} & \{5,8\} \\ \{2,7\} & \{3,10\} & \{4,8\} & \{5,6\} & \{1,9\} \\ \{3,8\} & \{4,6\} & \{5,9\} & \{1,7\} & \{2,10\} \\ \{4,9\} & \{5,7\} & \{1,10\} & \{2,8\} & \{3,6\} \\ \{5,10\} & \{1,8\} & \{2,6\} & \{3,9\} & \{4,7\} \end{array}
Finding an orthogonal pair of $6\times 6$ Latin squares is known as the "thirty-six officers problem", which has no solution. So there is no labeling of $K_{6,6}$ with the additional restriction that every pair must have a small and a large element. However, here is a $6 \times 6$ solution without that restriction, which I generated by simulated annealing in Mathematica:
\begin{array}{cccccc} \{2,10\} & \{5,9\} & \{7,8\} & \{3,11\} & \{6,12\} & \{1,4\} \\ \{1,7\} & \{3,10\} & \{5,12\} & \{2,4\} & \{9,11\} & \{6,8\} \\ \{4,8\} & \{2,11\} & \{6,9\} & \{1,10\} & \{3,5\} & \{7,12\} \\ \{5,11\} & \{6,7\} & \{4,10\} & \{8,12\} & \{1,2\} & \{3,9\} \\ \{3,6\} & \{4,12\} & \{1,11\} & \{7,9\} & \{8,10\} & \{2,5\} \\ \{9,12\} & \{1,8\} & \{2,3\} & \{5,6\} & \{4,7\} & \{10,11\} \\ \end{array}
(It looks like we already knew that such a labeling exists, but I wanted my answer to be complete.)