A recent question on MathOverflow (since closed) discusses a Japanese pencil-and-paper puzzle, 連環の数 (renkan-no-suu, 'chain of numbers') where the goal is to assign the numbers $1\ldots 2n-1$ to all the regions in a line of $n$ linked circles such that the value in each overlapping area is the sum of the values in the two circles to either side of it. As taken from what appears to be the original publication:
etc. Obviously there's nothing requiring the shapes to all be in a straight line, and since circle diagrams are going to get confusing fast, let's define a renkan labeling of a (connected) graph to be a labeling of all the vertices and all the edges with a permutation of the numbers $\{1\ldots |V|+|E|\}$ such that the label on each edge is the sum of the labels of the two vertices that it links; the original puzzle then corresponds to a straight-line graph of $n$ vertices (and $n-1$ edges). The natural question then arises: What graphs have (or don't have) renkan labelings?
The problem seems closely related to the notion of a graceful labeling of a graph, though there's no direct mapping from one to the other. The original MO poster claimed to have a way of labeling any chain graph like those in the original puzzle; I haven't been able to piece one together myself, though I can easily believe that one exists; even aside from a potential pattern it seems that the number of solutions grows rapidly with the number of vertices in the chain.
On the other hand, it's not too hard to provide examples of graphs that don't have labelings. While $K_3 (\equiv C_3)$ does have a labeling, one that's forced (put 1 and 2 on vertices; 3 must go on the edge between them, and then 4 must be a vertex, which puts 5 and 6 on its edges to 1 and 2), continuing the argument shows that $K_4$ can't have a valid labeling (7 would then have to go on the 4th vertex, and that provides labels for 8, 9, and 11, but not 10). This example also shows that having a labeling isn't preserved by taking (induced) subgraphs, since adding a single vertex adjacent to the one labeled 2 and labeling it 10 both covers the missing label and assigns the 'correct' label 12 to the new edge. (This also shows the lack of any isomorphism between graceful labelings and renkan labelings, since $K_4$ is graceful.)
Another instructive counterexample is the $C_5$ cycle graph: this can be shown impossible by a double-counting argument. If the vertices are labeled with numbers $v_1\ldots v_5$, then the values on the edges are $v_1+v_2, v_2+v_3, \ldots, v_5+v_1$ and therefore the total sum of all the labels is $3\sum_iv_i$ — but the sum of the numbers $1\ldots 10$ is $55$, which isn't a multiple of $3$. More generally, this same shows that no $C_n$ with $n\equiv 2\pmod 3$ can have a labeling; my searches have found labelings for all other $C_n$ with $n\leq 16$, though, and it seems likely (but would be nice to prove) that all other cyclic graphs have labelings.
Similarly, applying the same double-counting argument to graphs of any fixed degree provides specific modular constraints on the number of vertices; for instance, cubic graphs on $2n$ nodes have a sum of all labels $4\sum_iv_i$ by adding the contributions of a vertex to each of its edges and itself, and $|V|+|E|=5n$, so the sum of all labels is also $\frac125n(5n+1)$; this implies that either $5n$ or $5n+1$ is $\equiv 0\pmod 8$, so $n$ must be $\equiv0$ or $\equiv 3\pmod 8$. Among the six-vertex cubic graphs only $K_{3,3}$ has a labeling, but several 16-vertex cubic graphs do: both the octagonal prism graph and the generalized Petersen graph on 16 vertices do, for instance. Is there a 'natural' (and potentially generalizable) explanation for why the other 6-vertex cubic graph (the triangular prism graph) doesn't have a labeling? On the other side of the coin, are there labelable regular graphs of degree $d$ with $n$ vertices for all $d$ and all sufficiently large $n$ that meet the appropriate divisibility constraint?
And finally, and really the primary question of this (rather extended) post: tests show that every tree on $\leq 11$ vertices, and every tree of maximum degree three on $\leq 13$ vertices, has a labeling. Do all trees have a renkan labeling? (This would obviously imply the result for the linear case)
I am the original poster on MathOverflow. Thank you for putting the problem in the language of graph theory. By the clue of graph theory, I have obtained important information from my colleague.
Bange, Barkauskas, and Slater [BBS] introduced "k-sequentially additive" graph. Especially when k=1, 1-sequentially additive graph is also called a "simple sequentially additive" (SSA) graph. SSA graph has the exact same definition as renkan labeling!
In [BBS], a cycle graph $C_n$ is an SSA graph iff $n \equiv 0,1$ (mod 3). By preparing three different parts and dividing the problem into six cases, they gave specific labeling for $C_n$ when $n\equiv0,1$.
By cutting off $C_n$ or $C_{n+1}$, it is shown that the path (the straight-line graph) $P_n$ is a SSA graph for all n. This result for $P_n$ seems to be very different to my construction, however anyway the renkan puzzle had been already solved!
In addition, [BBS] also conjecture that all trees are SSA graphs. I do not know the conjecture is solved or not.
[BBS] D. Bange, A. Barkauskas, and P. Slater, Sequentially additive graphs, Discrete Math., 44 (1983) 235-241. https://www.sciencedirect.com/science/article/pii/0012365X83901875