For even $n$ we get an example with induction. For odd $n$, assume that there exist an example for an odd $n$. Take the least possible $n$. Then, we can divide the graph into two parts so that the condition of the problem is still satisfied. One of the subgraphs has an odd number of vertex.

egxa wrote: For even $n$ we get an example with induction. For odd $n$, assume that there exist an example for an odd $n$. Take the least possible $n$. Then, we can divide the graph into two parts so that the condition of the problem is still satisfied. One of the subgraphs has an odd number of vertex. perhaps can you give the solution instead?

Here's my long solution in the exam: Answer: $n$ is even Proof that odd numbers do not satisfy: We will make induction. When $n=3$ let edges be $a,b$ and $c$ from the $(ii)$ condition $a+b=b+c=c+a \implies a=b=c$ but this doesn't satisfys $(i)$ condition. Let for n=2k-1 doesn't satisfies conditions . Based on this, let's prove that doesn't satisfies for n=2k+1 either. Assume otherwise. Assume that there is an example that satisfies the conditions for $n=2k+1$. Consider the graph $G$ that satisfies those conditions. Let $a$ be the largest number written on any edge in this graph. Let's take one of the edges with $a$ written on it, let it be the edge between the vertices $X$ and $Y$. When you remove $X$, $Y$ and the edges coming from these vertices from the graph $G$, let the remaining graph be $G_1$. Let $(V_1,V_2)=$edge between $V_1$ and $V_2$, $|(V_1,V_2)|=$number that written on the edge $(V_1,V_2)$ then this lemma holds: Lemma:For all $v\in G_1$ there exist an constant integer b that satisfies $|(v,X)|=|(v,Y)|=b<a$ Proof: Since $a$ is the maximum number. This is obvious from condition $(i)$ Let $S_v=$ for $v\in G_1$ weight of $v$ with edges that in $G_1$ then for all $v$ vertices $S_v$ is equal to constant $S$. Because: For $G$ graph weights of vertices that also in $v$ equal to $S_v+2b$. Now let's look $G_1$ graph. Obviously that graph satisfies condition $(i)$ and condition $(ii)$. But we assumed for $n=2k-1$ there is no graph that satisfies the conditions, then contradiction. Proof for even numbers satisfies: We will make induction for this too. When $n=4$ let vertices are $A,B,C$ and $ D$ then if $|(A,B)|=|(B,C)|=|(C,D)|=|(D,A)|=1$ and $|(A,C)|=|(B,D)|=2$ this graph satisfies both condition. Let's assume that there is a graph exist that satisfies conditions for $n=2k$. We will show there is a graph exist for $n=2k+2$ too. Let $G$ be the graph that example for $n=2k$. Let's take vertices $X$ and $Y$ outside of $G$. If $c$ be the smallest number written on any edge in this graph for d<c let for all vertices $v\in G$ $|(v,X)|=|(v,Y)|=d$. And if the weight of all vertices in $G$ is S let $|(X,Y)|=S-2(k-1)d$. Let's show that graph $G$ with $X$ and $Y$ satisfies conditions. Condition (i):When we choose $X,Y$ and the any other vertex(other case are obvious from definition of $d$) if $S-2(k-1)d > d$ then it will satisfy. Let's show this. From definition of $d$: $S>2kd \implies S-2(k-1)d>d$ Condition $(ii)$: Weight of $X$ and $Y$ is equal to $2kd+S-2(k-1)d=S+2d$. Also for the other vertices their weight is $S+2d$ Proof completed.

Here are the details of an approach similar to the solution by egxa The answer is all even $n$. Part I: There exists a valid labeling for even $n$. Notice that a construction for $K_2$ is trivial. Now we will show that if there exists a valid labeling for $K_n$, then there also exists a valid labeling for $K_{n+2}$. Consider a labeling of $K_n$ with all entries shifted to be positive. Let $s$ be the weight of the vertices of $K_n$. Introduce two more points $P$ and $Q$. Assign the edge $PQ$ the label $s$ and all other edges connecting one of $P$ and $Q$ with a vertex from $K_n$ with the label $0$. Then this labeling on $n+2$ vertices clearly satisfies, and the result follows by induction. Part II: There does not exist a valid labeling for odd $n$. Let $m$ be the minimal real number assigned to an edge. Consider the set $S$ of all edges that are not labeled with $m$. Then notice that any triangle must have exactly $1$ or $3$ edges in $S$. As no triangle can have all edges labeled with $m$ and if two edges have an equal label larger than $m$ then the last side can not be labeled with $m$. We now show that any connected component of $S$ is in fact a complete graph. Choose two vertices $P$ and $Q$ in this portion. As this portion is connected, we can chose distinct vertices $v_1,\dots, v_k$ such that $P,v_1,\dots, v_k,Q$ is a path in $S$. As $Pv_1$ and $v_1v_2$ are edges, $Pv_2$ must also lie in $S$ and continuing in this manner $PQ$ lies in $S$, as desired. Thus $S$ is the union of disjoint complete sub-graphs. As every vertex must have an adjacent edge that lies in $S$ (otherwise the weight of that vertex will be strictly smaller), every vertex must lie in one of these disjoint complete sub-graphs. Then, as we must not be able to choose three vertices that all lie in different subgraphs, there must be exactly two complete subgraphs, each with at least two vertices. Notice one of these graphs must also have odd size. Thus we can repeat the process with this smaller odd complete graph. Eventually, we get to $n=3$, reaching a contradiction.

turkOklid wrote: Here's my long solution in the exam: Answer: $n$ is even Proof that odd numbers do not satisfy: We will make induction. When $n=3$ let edges be $a,b$ and $c$ from the $(ii)$ condition $a+b=b+c=c+a \implies a=b=c$ but this doesn't satisfys $(i)$ condition. Let for n=2k-1 doesn't satisfies conditions . Based on this, let's prove that doesn't satisfies for n=2k+1 either. Assume otherwise. Assume that there is an example that satisfies the conditions for $n=2k+1$. Consider the graph $G$ that satisfies those conditions. Let $a$ be the largest number written on any edge in this graph. Let's take one of the edges with $a$ written on it, let it be the edge between the vertices $X$ and $Y$. When you remove $X$, $Y$ and the edges coming from these vertices from the graph $G$, let the remaining graph be $G_1$. Let $(V_1,V_2)=$edge between $V_1$ and $V_2$, $|(V_1,V_2)|=$number that written on the edge $(V_1,V_2)$ then this lemma holds: Lemma:For all $v\in G_1$ there exist an constant integer b that satisfies $|(v,X)|=|(v,Y)|=b<a$ Proof: Since $a$ is the maximum number. This is obvious from condition $(i)$ Let $S_v=$ for $v\in G_1$ weight of $v$ with edges that in $G_1$ then for all $v$ vertices $S_v$ is equal to constant $S$. Because: For $G$ graph weights of vertices that also in $v$ equal to $S_v+2b$. Now let's look $G_1$ graph. Obviously that graph satisfies condition $(i)$ and condition $(ii)$. But we assumed for $n=2k-1$ there is no graph that satisfies the conditions, then contradiction. Proof for even numbers satisfies: We will make induction for this too. When $n=4$ let vertices are $A,B,C$ and $ D$ then if $|(A,B)|=|(B,C)|=|(C,D)|=|(D,A)|=1$ and $|(A,C)|=|(B,D)|=2$ this graph satisfies both condition. Let's assume that there is a graph exist that satisfies conditions for $n=2k$. We will show there is a graph exist for $n=2k+2$ too. Let $G$ be the graph that example for $n=2k$. Let's take vertices $X$ and $Y$ outside of $G$. If $c$ be the smallest number written on any edge in this graph for d<c let for all vertices $v\in G$ $|(v,X)|=|(v,Y)|=d$. And if the weight of all vertices in $G$ is S let $|(X,Y)|=S-2(k-1)d$. Let's show that graph $G$ with $X$ and $Y$ satisfies conditions. Condition (i):When we choose $X,Y$ and the any other vertex(other case are obvious from definition of $d$) if $S-2(k-1)d > d$ then it will satisfy. Let's show this. From definition of $d$: $S>2kd \implies S-2(k-1)d>d$ Condition $(ii)$: Weight of $X$ and $Y$ is equal to $2kd+S-2(k-1)d=S+2d$. Also for the other vertices their weight is $S+2d$ Proof completed. Ohhh... I think my solution is not correct. I said $|(v,X)|=|(v,Y)|$ equal to constant b for every $v$ But it's not true.

As the title says the problem is slightly tricky, but it isn't outright hard. I'm supposed to be bad at combinatorics but I enjoyed this problem all the same. My approach is similar to the solutions above. We claim that the answer is all even $n\ge 4$. We start off by showing that these $n$ indeed work, which we shall do via induction. Let $n$ be called balanced, if such an assignment of numbers to edges exists. First note that $4$ is balanced. We can simply assign $1$ to each 'side' of the quadrilateral and $2$ to each 'diagonal', which satisfies all the required conditions. Note how $1$ is the minimum edge number and $4=1\times 4$ is the weight of each vertex. Now, say an even integer $n$ is balanced with minimum edge number $\frac{W}{n}$ where $W$ is the common weight. Let $x= \frac{W}{n+1}$. Now consider $K_{n+2}$ with a subgraph of $n$ vertices $K_n$. Assign weights to $K_n$ is order to satisfy the conditions for this $K_n$ subgraph. Let the other two vertices be $v_1$ and $v_2$. For any vertex $u \in K_n$ assign weights $x$ to the edges $u-v_1$ , $u-v_2$. To the edge $v_1-v_2$ assign the number $2x$. We leave it to the reader to engage in the entertaining task of checking that the $K_{n+2}$ graph also satisfies all the conditions with minimum edge number $\frac{W'}{n+2}$ where $W'$ is the new common weight. We now show that no odd integer $n$ can be balanced. It is fairly clear that $3$ is not balanced since two edges are assigned a real number $a$ and the other $b>a$ we have $2a>a+b$ so the weights cannot be equal. By way of contradiction assume that $n>3$ is the smallest odd balanced integer. Consider a vertex $v$ in $K_n$ and arrange all other vertices $u$ in $K_n$ in increasing order of the number assigned to the edge $v-u$ , $m_1 < m_2 < \dots < m_i$. If any of these are negative we add a sufficiently large number to each number assigned to the edges, which preserves both conditions. We first need to show a couple of properties regarding such an assignment. Let $a_k$ denote the number of vertices with edge number $m_k$. Claim : There exists a unique vertex $u$ such that $v-u$ is assigned $m_i$ (the highest number). Proof : Consider the set of vertices $u,u_1,\dots,u_r$ such that $v-u$ etc. are assigned $m_i$. Consider an edge $u'-u$ such that $v-u'$ is assigned some number $m_j<m_i$. Considering triangle $(v-u-u')$ it is clear that edge $u-u'$ must be assigned $m_j$. Then the weight of vertex $v$ is, \[a_1m_1 + a_2m_2 + \dots + a_{i-1}m_{i-1}+a_im_i\]The weight of vertex $u$ is \[a_1m_1+a_2m_2+\dots + a_{i-1}m_{i-1}+S\]where $S$ is the sum of the numbers assigned to edges $u-u_t$ for $1\le t \le r$. Note that due to triangles $(v-u_t-u)$ each number assigned to an edge $u-u_t$ is greater than $m_i$. Thus, $S>a_im_i$ which implies that, \[a_1m_1+a_2m_2+\dots + a_{i-1}m_{i-1}+S > a_1m_1 + a_2m_2 + \dots + a_{i-1}m_{i-1}+a_im_i\]which is a clear contradiction, which proves the claim. Claim : For each number $m_j$, there cannot exit exactly one vertex $u$ such that $v-u$ is assigned $m_j$ ($m_j<m_i$). Proof : Say there exists such a vertex. Then due to the previous observation, the weight of vertex $u$ is, \[a_1m_1+\dots + a_{j-1}m_{j-1}+m_j + (a_{j-1}+\dots + a_i)m_i < a_1m_1 + \dots + a_im_i\]which is the weight of vertex $v$. Claim : Let $G$ denote the graph among the vertices $u_t$ for $1\le t \le r$ which all are assigned $m_k$ for some fixed constant $k$ at the edge $v-u_t$. Proof : This is quite clear. The first condition must obviously be satisfied by $G$ since it is a subgraph of $K_n$. The second condition is also required since due to our previous observation, the number assigned to each edge $u_t-u$ for $u \not \in G$ is determined by $u$ and hence the sum of such numbers is common to all $u_t$, implying that the sum of the numbers among themselves must be equal. Now, note that since $a_1+a_2+\dots + a_{i-1}=n-2$ which is odd, one of these indices $a_k>1$ is odd. But then due to the third claim, we have a smaller odd balanced integer than $n$ which is a contradiction. Thus, no such integer exists and we are done.