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.