Is it possible to put $\binom{n}{2}$ consecutive natural numbers on the edges of a complete graph with $n$ vertices in a way that for every path (or cycle) of length $3$ where the numbers $a,b$ and $c$ are written on its edges (edge $b$ is between edges $c$ and $a$), $b$ is divisible by the greatest common divisor of the numbers $a$ and $c$? Proposed by Morteza Saghafian
Problem
Source: Iran TST 2012-Second exam-1st day-P1
Tags: induction, graph theory, greatest common divisor, combinatorics proposed, combinatorics
14.05.2012 03:54
For $n=2$ take an edge with number $1$. For $n=3$ take $K_3$ with numbers $1,2,3$. Now assume $n \ge 4$ Let $S_k$ be the set of edges with numbers that are divisible by $k$, and suppose $|S_k| \ge 2$. For any two edges in $S_k$, a third edge that is incident with both must have a number divisible by $k$ by the condition. So the edges of $S_k$ form a complete graph. That is $|S_k| = \binom{m_k}{2}$. Now take a number $r$ that such that $\frac{1}{r}\binom{n}{2}=p$ is a prime. Since the numbers among all edges are consecutive there are exactly $p$ edges with numbers divisible by $r$. So $\binom{m_r}{2} = p$, hence $p=3$. So in fact $\binom{n}{2}=3^s$ for some $s$. But by the uniqueness of base three representations we can show this is impossible for $n>3$ So the answer is true for $n=2,3$ and false for $n>3$
14.05.2012 06:53
Or you could use induction after proving that $S_k$ is a complete graph. Even numbers form a clique, so dividing all of the numbers on the clique by $2$, we get a graph satisfying Problems conditions, and also with less vertices
16.05.2012 16:46
goodar2006 wrote: Is it possible to put $\binom{n}{2}$ consecutive natural numbers on the edges of a complete graph with $n$ vertices in a way that for every path (or cycle) of length $3$ where the numbers $a,b$ and $c$ are written on its edges (edge $b$ is between edges $c$ and $a$), $b$ is divisible by the greatest common divisor of the numbers $a$ and $c$? goodi in soalo be onvan nazarie adad to emtehan dadan...
20.05.2012 19:40
Seems someone is wrong ( his sol. of my enterpretation): Take $(2,4,6)$ on the $K_3$ and connect the edge with $2,4$ with a side of number $3.$ We have $4$ triples of cycles/ triangles: $(2,4,6),(4,3,1),(6,5,1),(2,3,5)$ and the problem holds for $n=4.$ Goodar, what did u mean with that and does someone know sure about the solution?
20.05.2012 19:46
SCP wrote: Seems someone is wrong ( his sol. of my enterpretation): Take $(2,4,6)$ on the $K_3$ and connect the edge with $2,4$ with a side of number $3.$ We have $4$ triples of cycles/ triangles: $(2,4,6),(4,3,1),(6,5,1),(2,3,5)$ and the problem holds for $n=4.$ Goodar, what did u mean with that and does someone know sure about the solution? Are you sure? Have you checked the paths of length three? goodar2006 wrote: Is it possible to put $\binom{n}{2}$ consecutive natural numbers on the edges of a complete graph with $n$ vertices in a way that for every path (or cycle) of length $3$ where the numbers $a,b$ and $c$ are written on its edges (edge $b$ is between edges $c$ and $a$), $b$ is divisible by the greatest common divisor of the numbers $a$ and $c$? Proposed by Morteza Saghafian
01.05.2013 16:44
this might be wrong because it's too short but i can't find a flaw. for $n\ge 5$ if $k=\binom {n}{2}$ and we consider the at least $4$ and at most $5$ numbers divisible by $[k/4]$ to get an easy contradiction. and for $n=4$ exactly $2$ numbers are divisible by $3$ again giving a contradiction. of course for $n=3$ we may choose any $3$ consecutive numbers $k,k+1,k+2$ where $2|k+1$. if $n=1$ then it's just a vertex and for $n=2$ take any number $k$. Sorry if i repeated the above posts.
17.08.2020 22:00
Solved with eisirrational and goodbear. The answer is yes if and only if $n \leq 3$, all of which clearly work. The following is the main structural claim. Claim. For any integer $d$, the edges divisible by $d$ form a complete graph. Proof. Take the subgraph $G'$ formed by taking the edges divisible by $d$ and consider a maximal clique. Then if $vx \in G'$ is not in the clique with $v$ in the clique, then $uvxu$ for $u,v$ in the clique implies $ux \in G'$ is divisible by $d$. Varying $u$ gives that $x$ is in the clique, a contradiction. Similarly, if $xy$ is not in the clique with $x,y$ not in the clique, then for any $u,v$ in the clique we take $uvxy$ and $uvyx$ to show $vx, vy \in G'$ and so $x,y$ in the clique, another contradiction. So $G'$ is the maximal clique, as desired. $\square$ Let $m = \binom{n}{2}$. Then there are either $\lfloor m/d\rfloor$ and $\lceil m/d \rceil$ edges divisible by $d$, which must be triangular. If $n \geq 5$, then taking $d = \lfloor m/4 \rfloor$ yields $\{4,5\}$, neither of which is triangular. For $n=3$ take $d = 3$.
02.08.2023 18:15
Fairly vacuous once you notice the main claim. The answer is yes if and only if $n \leq 3$, and the if direction is trivial. For the other direction, the key is the following: Claim. For any $k$, all edges divisible by $k$ form a clique. Proof. Given any configuration of edges, it follows that any edge that connects two edges or forms a cycle with two edges is also labeled as such. From here, an easy maximality (of edges) argument shows that the edges must form a clique. $\blacksquare$ Now just pick a $k$ with $4 \leq \frac{{n \choose 2}}k < 5$ to get a contradiction.