Suppose $ \,G\,$ is a connected graph with $ \,k\,$ edges. Prove that it is possible to label the edges $ 1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1. Note: Graph-Definition. A graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $ \,u,v\,$ belongs to at most one edge. The graph $ G$ is connected if for each pair of distinct vertices $ \,x,y\,$ there is some sequence of vertices $ \,x = v_{0},v_{1},v_{2},\cdots ,v_{m} = y\,$ such that each pair $ \,v_{i},v_{i + 1}\;(0\leq i < m)\,$ is joined by an edge of $ \,G$.
Problem
Source: IMO 1991, Day 2, Problem 4, IMO ShortList 1991, Problem 10 (USA 5)
Tags: number theory, greatest common divisor, Euler, graph theory, combinatorics, IMO, imo 1991
Peter
14.11.2005 03:45
This is the problem that made our graph theory teacher study graph theory (mario pickavet, bronze '91)
Start at any vertex A and number 1,2,3,... along any path. every vertex you pass will have edges k,k+1 so has gcd=1, until you reach a dead end. (which is either a vertex with degree 1 (no prob) or a vertex on which all edges are labeled yet (no prob). Now if there are unlabeled edges left, start at any vertex of such an edge, and repeat the procedure. Like that you can fill the graph such that all vertices have gcd(edges)=1.
gcd(2,3,6)=1...
perfect_radio
24.08.2006 01:18
Can I make a small remark? It's kind of late now, maybe I'm missing something obvious.
I tried to solve the problem. But it didn't cross my mind such a simple trick. Maybe I should try solving problems at not so late hours.
So, about what we do after going through the first path:
We suppose that we're not done. Can we choose that "such an edge" just randomly, and then wander through the graph until we reach a dead-end? I don't think we can do it, maybe Peter thought that what should be done was obvious, but I'm trying to find out if I got it right.
Let $x_{1},\ldots,x_{t}$ be the vertices involved in the path. If $t=n$, just put random numbers on the other edges. Else let $v$ be another vertex. We can find a path $x_{1}, \ldots, v$, which we truncate to $x_{p},y_{1},\ldots,y_{s},v$, where $y_{1},\ldots,y_{s}$ are not among the $x_{i}$'s. None of the edges in between have been labeled, so we can safely repeat the procedure on that path, then upon reaching $v$ we "randomize". This increases the number of vertices involved by at least $1$, so, after finitely many steps, $t$ will be equal to $n$, in which case we do as above, i.e. label the remaining edges randomly as they don't matter.
Peter
24.08.2006 12:41
I don't see your point... where would I use non-randomness? Note that we are labeling edges, not vertices. Either a vertex has only one edge (in which case there's nothing to prove), or either there are at least 2, and by the algorithm we will ever run through it and make that vertex thus have at least 2 coprime edges.
tim1234133
25.08.2006 21:02
I don't think this is the point that perfect_radio is making, but anyway... I don't see where your proof uses connectivity. When we have gone through the first set of labelling, you say that if there are unlabelled edges (Sorry about the typo that was here...) 'start at any vertex of such an edge'. How do we know that this vertex (the one we start on the second time we make a path) has gcd(edges)=1? Can we get round this by saying 'start at a vertex that has some already labelled vertices', and hence use the fact that the graph is connected? Or am I just missing something altogether?
JBL
25.08.2006 21:07
tim1234133 wrote: I don't think this is the point that perfect_radio is making, but anyway... I don't see where your proof uses connectivity. When we have gone through the first set of labelling, you say that if there are unlabelled vertices 'start at any vertex of such an edge'. How do we know that this vertex (the one we start on the second time we make a path) has gcd(edges)=1? Can we get round this by saying 'start at a vertex that has some already labelled vertices', and hence use the fact that the graph is connected? Or am I just missing something altogether? "Start at a vertex that has already labelled edges" is what he meant. Such a vertex exists by connectivity.
Peter
25.08.2006 21:25
[here was a wrong idea, thx tim1234133.] For the rest of your remark, tim1234133, I will say it again: we are labeling edges, NOT vertices. If it was only a typo please reformulate your question in the right way as there are many interpretations possible.
tim1234133
25.08.2006 22:25
How do we label the (unconnected) graph formed of two unconnected triangles (If we call the vertices A-F we have A connected to B and C with B and C also connected to each other, and D connected to E and F with E and F connected to each other) in the required manner?
Peter
25.08.2006 22:37
Err... never mind, we really need connectedness indeed.
perfect_radio
30.08.2006 22:03
Yes, that was also my point. It's too bad I couldn't explain it in a more understandable manner
GoldenFrog1618
11.06.2010 23:12
I will induct on the number of edges and keep the number of verticies fixed. For a base case, we need to prove that all trees can be labeled. Notice that there is a path between all the verticies of degree >=2. Thus, we should label these edges in order 1,2,3,4 ..., n. (Include the two edges connected to a vertex of degree 1). Call vertex with no edges labeled "unlabeled" since any permutation of the labels will work. Note that there are only 2 labeled degree one verticies. Now we progressively add edges to the graph until we get the desired number of edges. Case 1: A vertex of degree >=2 connected to a vertex of degree >=2. There is nothing needed to be done. Case 2: An unlabeled vertex of degree 1 connected to a vertex of degree >=2. Label the new edge and the unlabeled edge two consectutive numbers. Case 3: An unlabeled vertex of degree 1 connected to an unlabeled vertex of degree 1. Label the two unlabeled edges and the new edge three consecutive numbers. Case 4: A labeled vertex of degree 1 connected to a vertex of degree >=2. Label this new edge either n+1 if the label is n or keep it unlabeled if the label is 1. Case 5: A labled vertex of degree 1 connected to a labeled vertex of degree 1. Label the connection n+1. Case 6: A labeled vertex of degree 1 connected to an unlabeled vertex of degree 1. If the labled edge is n, label the two edges n+1 and n+2 (increase other edges if necessary). If the labled edge is 1, label the two edges consecutive numbers. Notice that there are at most two instances of connecting a labeled vertex to another vertex, so we are done.
shekast-istadegi
05.07.2012 19:00
This is easy probelm_hint_>we are doing the graph Euler Garlic by Connect odd edges of the graph and we use induaction.
Generic_Username
04.01.2017 03:09
Arbitrarily order the vertices. If a vertex has degree $1$ and $k$ vertices have been labelled, label the unique edge $k+1.$ Otherwise, label the edges $k+1,k+2,\cdots, k+\text{deg}(v).$ Since $\gcd(n,n+1)=1\ \forall\ n,$ we are done.
dgrozev
04.01.2017 15:36
It's not so trivial. Suppose, we have 4 vertices: $a,b,c,d$ s.t. $\{b,c,d\}$ are connected with each other and $a$ is connected only with $b$. Following the above, we label $ab$ as $1$; $bc, bd$ as $2$ and $3$ respectively and $cd$ as 4. Look at the vertex $c$, its edges are labeled as $2,4$ !?
yayups
01.09.2018 10:31
Not 100\% sure if this works, but here it is. It suffices to have two adjacent labels at every vertex. Consider the path of maximum length. Label its edges consecutively, and then color all the edges red. Now, consider the maximum length path in non-red edges and repeat. Call path $k$ the maximum length path that we chose on the $k$th iteration. We claim that this works. Note that all vertices that are not on the ends of any paths are automatically taken care of. The only potential issue is that there could be some vertex $v$ that is always only on the end of paths. If $v$ has degree $1$. then this isn't actually a problem. So suppose $v$ has degree at least $2$. It only appears on the end of paths, so there exist $i,j$ such that $v$ is on an end of path $i$ and path $j$ (WLOG $i<j$). But then, gluing together paths $i$ and $j$ results in a path of longer length at stage $i$ (all of path $j$ is still not red since it was not red at stage $j$). One possible issue is that if paths $i$ and $j$ also share their other respective ends, but this can easily solved by deleting one edge in the cycle that's formed when we glued them (still leads to a longer path on stage $i$). Therefore, we must have $\mathrm{deg}v=1$, so every vertex now has two adjacent labels adjacent to it. EDIT: This is wrong, consider a cycle. I will try to fix soon...
MathStudent2002
20.06.2019 04:59
Epic problem. Solution with ewan. Say all degrees are even. Then, we have an Eulerian circuit, which we just label $1, 2, \ldots, k$ in succession. Then, each vertex is labeled either with 2 consecutive integers or with $1$ and $k$ (or both) so we are done. Else, consider the graph $G'$ where we add edges to $G$ between pairs of odd-degree vertices. Then, $G'$ has an Eulerian circuit. Removing the added edges from the circuit turns it into a set of walks with union $E(G)$ such that each walk starts and ends at odd-degree vertices and each odd-degree is the endpoint of exactly one walk. Now, if the walks have lengths $k_1, \ldots, k_m$, then label the first one with $[1, k_1]$ in order, the second one with $[k_1+1, k_1+k_2]$, etc., and the last one with $[k_1+\cdots+k_{m-1}+1, k_1+\cdots+k_m]$. We see that each non-leaf vertex must appear in the interior (i.e. non-endpoint) of some walk and thus have two edges labeled with consecutive numbers, and hence have $\gcd$ of edge labels equal to one. $\blacksquare$
dgrozev
20.06.2019 13:26
MathStudent2002 wrote: ...Now, if the walks have lengths $k_1, \ldots, k_m$, then label the first one with $[1, k_1]$ in order, the second one with $[k_1+1, k_1+k_2]$, etc., and the last one with $[k_1+\cdots+k_{m-1}+1, k_1+\cdots+k_m]$. We see that each non-leaf vertex must appear in the interior (i.e. non-endpoint) of some walk and thus have two edges labeled with consecutive numbers, and hence have $\gcd$ of edge labels equal to one. $\blacksquare$ What if the second walk, for example, begins and ends to one and the same vertex? So you assign $k_1+1$ and $k_1+k_2$ to those first and last edges and of course the may not be coprime. I know it can be patched somehow, but then that idea of Euler cycles will lost its originality and it would be dissolved into something like in post #2.
Pathological
20.06.2019 15:35
I think what he/she is doing in the third paragraph is the following. Let $v_1, v_2, \cdots, v_{2t}$ be the vertices of odd degree of $G$ (there's an even number of them by the Handshake Lemma, say). If $t = 0$, then simply take an Eulerian cycle and label the edges $1, 2, \cdots, k$ in order. Otherwise, we will add the edges $v_1v_2, v_3v_4, \cdots, v_{2t-1} v_{2t}.$ Let this modified graph be $G'.$ Note that this may result in the graph not being simple anymore, but that's fine since the problem still holds. Now, observe that $G'$ has all degree evens, and hence contains an Eulerian cycle. Then, it's clear that the removal of $v_1v_2, v_3v_4, \cdots, v_{2t-1} v_{2t}$ from the cycle would partition the cycle into walks from $v_2$ to $v_3$, from $v_4$ to $v_5$, $\cdots$, from $v_{2t}$ to $v_1.$ This makes it such that none of the walks can be cycles since the $v_i$'s are distinct, and so we finish as above. Edit: Also, as far as I can tell, the idea in post #2 does not work, since it does not account for cycles (what if the walk ends at the same vertex it began with, and we label the edges $2, 3, 4$?). The solution in post #16, on the other hand, obviates the possibility of cycles using the odd degree trick.
SnowPanda
13.01.2022 21:51
Call a labelling of the edges of $G$ good if for every vertex with degree at least $2$, the greatest common divisor of its edges is $1$.
If $G$ is a cycle, then labelling the edges $1$, $2$, $\ldots$, $k$ in order works.
Claim: If $G$ is a tree with $k$ edges, then given any set $S$ of $k$ consecutive integers, there exists a good labelling of $G$ using the labels in $S$ (each used exactly once).
Proof. Use strong induction on $k$, with base case $k = 0$. Take a path between two leaves of $G$, and label it with the $\ell$ largest integers of $S$, in order. Then delete all the edges (but not vertices) of this path, which splits $G$ into some number of trees. Split the remaining elements of $S$ (which are all consecutive) so that each tree is assigned a consecutive set of elements of $S$, and take a good labelling for each of these smaller trees. Then any lone vertex or leaf in a smaller tree was either a leaf in $G$, or was on the path in $G$, so this is a good labelling of $G$ as well. $\blacksquare$
Now if $G$ is a tree or a cycle, it has a good labelling. Otherwise take any cycle $C = (v_1v_2\cdots v_c)$ where $v_1$ has an edge not in $C$. Create a graph $G'$ by adding a new vertex $v_{c + 1}$ and replacing the edge $v_cv_1$ with $v_cv_{c + 1}$. This keeps the graph connected, and any good labelling of $G'$ is also a good labelling of $G$ (since all vertices in $G$ still have degree at least $2$ in $G'$). So by inducting on $e - v + 1$ (with base case $0$) we're done.
vsamc
29.06.2023 05:14
We will prove this by strong induction on $k$.
If $k = 1$, then $G$ must be a single edge connecting two vertices, for which we can just place $1$ on that edge and all the conditions are satisfied.
Now, take some $r\geq 2$, and suppose that the problem is statement for $k = 1, 2, \cdots, r-1$. We will show that the statement is true for $k = r$. Consider the graph $G$ for $k = r$.
If there exists a vertex $v_1 \in G$ for which $\deg v_1 = 1$, then do the following: Let $v_2$ be the neighbor of $v_1$. If $\deg v_2 > 2$, then stop. Else, if $\deg v_2 = 2$, then let $v_3$ be the other neighbor of $v_2$. Repeat a similar process for $v_3$ and carry on.
Then, we have a path $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_\ell$ for which $\deg v_1 = 1$, and $\deg v_2 = \deg v_3 = \cdots = \deg v_{\ell-1} = 2$, $v_i$ is connected to $v_{i+1}$, and $\deg v_{\ell} \neq 2$. Then, label the edge $v_1v_2$ with $k$, $v_2v_3$ with $k-1$, $\cdots$, $v_{\ell-1}v_{\ell}$ with $k - \ell + 2$. Then, the labeled on each $v_k$ for $2\leq k\leq \ell-1$ differ by $1$, so their gcd is $1$. Thus, the condition is satisfied for all such $v_k$. Now, take the induced graph determined by removing $v_1, v_2, \cdots, v_{\ell-1}$. This graph would have $k - (\ell - 1) = k-\ell+1$ edges, and is obviously still connected, unless it is empty. If it is empty then $G$ is just the path $v_1\rightarrow v_2\rightarrow \cdots \rightarrow v_{\ell}$, and $\deg v_1 = \deg v_{\ell} = 1$, so the condition does not apply for those vertices, and we have shown that the condition holds for all other vertices, so we're done in that case. Else, we have that $\deg v_{\ell} \geq 3$, and the induced graph is nonempty and connected. Then, by the inductive hypothesis, we can label each edge of the induced graph $1, 2, \cdots, k-\ell+1$ so that the condition is satisfied. Now, consider these labelings in conjunction with our labelings of the other edges. We know that the labelings are fine for $v_1v_2, v_2v_3, \cdots, v_{\ell-2}v_{\ell-1}$ since they do not change based upon the labelings of the induced graph since they are only adjacent to other $v_iv_{i+1}$'s, and we know that the labelings are fine in the induced graph for every edge that is not connected to $v_{\ell}$. For $v_{\ell}$, note that the degree of $v_{\ell}$ in the induced graph is at least $2$, so the gcd of the edges connected to $v_{\ell}$ in the induced graph is $1$, and so the gcd of the labels in $v_{\ell}$ in $G$ is also $1$, since $\gcd(a_1, a_2, \cdots, a_{n+1}) \mid \gcd(a_1, a_2, \cdots, a_n)$, and the former must be $1$ if the latter is $1$. Thus, this edge labeling works if there exists a vertex $v_1 \in G$ for which $\deg v_1 = 1$.
If there does not exist a vertex $v\in G$ for which $\deg v = 1$, then for all $v\in G$, we have that $\deg v\geq 2$. Thus, there exists a cycle of length at least $2+1 = 3$ in $G$ (well-known fact that there exists a cycle of length $\text{mindeg } v+1$ in a graph). Let $c_1\rightarrow c_2\rightarrow \cdots \rightarrow c_{\ell}$ be a cycle in $G$, for some $\ell \geq 3$. If there exists more than one $c_i$ with $\deg c_i \geq 3$, then let $i_1$ be the smallest such index for which $\deg c_{i_1} \geq 3$, and let $i_2$ be the second-smallest such index for which $\deg c_{i_2} \geq 3$. Then, consider the path $c_{i_1} \rightarrow c_{i_1+1}\rightarrow \cdots \rightarrow c_{i_2}$. Note that for any $i_1 < j < i_2$, we have that $\deg c_j = 2$ by minimality of $i_1$, $i_2$. Now, label the edge $c_{i_1}c_{i_1+1}$ with $k$, $c_{i_1+1}c_{i_1+2}$ with $k-1$, $\cdots$, $c_{i_2-1}c_{i_2}$ with $k - (i_2-i_1-1)$, and consider the graph determined by removing all of those edges, and remove the vertices $c_{i_1+1}, c_{i_1+2}, \cdots, c_{i_2-1}$ (these vertices have degree $0$ after the removal of the edges since they had degree $2$ earlier). Then, the resulting graph is still connected, since you can get from one side to the other in the cycle by using the other direction, and it has $k - (i_2-i_1)$ edges. Thus, by the inductive hypothesis we can label the edges $1, 2, \cdots, k - (i_2-i_1)$ so that the condition is satisfied for the reduced graph. Now, consider the entire graph. Then, for each vertex $v\notin \{c_{i_1}, c_{i_1+1}, \cdots, c_{i_2}\}$, we have that the condition is satisfied for $v$ since it was satisfied in the reduced graph and no new edges are added to it. For $c_{i_1+1}, c_{i_1+2}, \cdots, c_{i_2-1}$, thy all have degree two and their labels are adjacent numbers (so they have gcd $1$). For $c_{i_1}$ and $c_{i_2}$, they have degree at least $3$, so they must have had degree at least $2$ in the reduced graph, and so the gcd of the labels in the reduced graph is $1$. Thus, since $\gcd(a_1, a_2, \cdots, a_{n+1}) \mid \gcd(a_1, a_2, \cdots, a_n)$, the former must be one if the latter is $1$, so the gcd is $1$ for $c_{i_1}$ and $c_{i_2}$ in $G$ as well. Thus, this edge labeling works if there are two vertices in the cycle with degree at least $3$.
If all vertices in the cycle have degree $2$, then $G$ must be just that cycle since $G$ is connected. Thus, we can just labeled the edges $1, 2, \cdots, k$ in that order and it clearly works.
Else, there is exactly one edge in the cycle with degree $3$, say $v_1$. Let $v_1, v_2, \cdots, v_r$ be the vertices in the cycle. Then, label $v_1v_2$ with $k$, $v_2v_3$ with $k-1$, $\cdots$, $v_{r-1}v_r$ with $k-(r-2)$, and $v_rv_1$ with $k - (r-1)$. Now, if $\deg v_1 > 3$, then we can just remove all the edges $v_iv_{i+1}$ and $v_rv_1$, and the vertices $v_2, \cdots, v_r$ to get a connected graph on $k-r$ edges, so we can label the edges $1, 2, \cdots, k-r$ so that it works on the reduced graph. Now, it is not hard to see that it works in the original graph -- for all vertices which are not a $v_i$, it works because no new edges are added. For all vertices which are $v_i$ for $i\neq 1$, it works because its two labels on the two edges emanating from it are adjacent, so their gcd is $1$. For $v_1$, note that in the reduced graph, the degree of $v_1$ is $>1$ (so it is $\geq 2$), so the gcds of the labels in the reduced graph is $1$, and so the gcds of the labels in $G$ is $1$ since $\gcd(a_1, a_2, \cdots, a_{n+1}) \mid \gcd(a_1, a_2, \cdots, a_n)$ as discussed before many many times. Else, $\deg v_1 = 3$. Do the same thing as we did in the degree $1$ case in the beginning to get a path $v_1 \rightarrow v_{1,2} \rightarrow v_{1,3} \rightarrow \cdots \rightarrow v_{1, \ell}$ for which $\deg v_1 = 3$, $\deg v_{1,2} = \deg v_{1,3} = \cdots = \deg v_{1, \ell-1} = 2$, and $\deg v_{1,\ell} \neq 2$. Then, label the edge $v_1v_{1,2}$ with $k-r$, the edge $v_{1,2}v_{1,3}$ with $k-(r+1)$, $\cdots$, the edge $v_{1, \ell-1}v_{1, \ell}$ with $k-(r+\ell-2)$. If $\deg v_{1,\ell} = 1$, then since $G$ is connected, then $G$ is just the path + the cycle, and it is not hard to see that the labeling works since the gcd of two adjacent numbers is $1$. Else, if $\deg v_{1, \ell} \geq 3$, then take the induced graph determined by removing $v_1, v_2, \cdots, v_r$, $v_{1, 2}, v_{1, 3}, \cdots, v_{1, \ell-1}$, and all edges that these vertices had, and then the remaining graph is a connected one on $k-(r+\ell - 1)$ edges, so by the inductive hypothesis we can label it and then this labeling works for $G$, since for every vertex not in the $v_i$ or the $v_{1, j}$'s, no new edges are added when we go from the induced graph to $G$, we already showed everything in the cycle works besides $v_1$, $v_1$ works since two of its edges are labeled $k-(r-1)$ and $k-r$, $v_{1,2}, v_{1, 3}, \cdots, v_{1, \ell-1}$ all work since their neighboring edges have labels that are adjacent numbers (and so they have gcd $1$), and $v_{\ell}$ works since it has degree at least $2$ in the inducted graph and we can use the same $\gcd(a_1, a_2, \cdots, a_{n+1}) \mid \gcd(a_1, a_2, \cdots, a_n)$ argument we have done several times before.
Thus, in all cases, our inductive step is complete and so we are done. $\blacksquare$
HamstPan38825
02.08.2023 18:02
The idea here is that fixing two edges around a vertex essentially makes it work, so we can work greedily. Call a vertex valid if we have labeled two edges through it with relatively prime indices. It suffices to make all vertices valid. Consider the longest walk in $G$, and label the edges along this walk in the order $1, 2, \dots, k$ consecutively. By maximality of the walk, every vertex in the walk (including the endpoints) is now valid; now, consider the subgraph $G'$ formed by removing all edges and any leaves in the walk, and continue the process until all edges are exhausted.
thdnder
06.09.2023 16:18
An inductive solution. Let $G = (V,E)$. We induct on $|V|$, assuming $|V| \geq 3$. Assume the problem statement is true on all connected graph with the number of vertices less than $|V|$. Since $G$ is connected, let $T$ be the spanning tree of $G$. Let $v$ be a leaf of $T$. Then $G-v$ is still connected, so by the induction hypothesis, we can label the edges of $G-v$ satisfying the problem condition. Let $\deg v = s$. Then if $s \geq 2$, $\gcd(k, k-1, \dots, k-s+1) = 1$ so labeling the remaining edges in arbitrary order will be satisfying the condition. Thus we're done.
kamatadu
01.01.2024 21:32
We induct with the base case being clearly true. If $G$ has a cycle and the cycle is connected to some other component, then there is a vertex with $\ge 3$ degree. Now remove an edge from this vertex thus breaking the cycle but the graph still remaining connected. Then by our induction hypothesis, we can get a number of the edges using $1,\ldots, k-1$. Now, after removing the edge, we note taht the gcd of the vertex $=1$. So adding back the removed edge, the $\gcd$ would still be $=1$. Now if the graph has only a cycle (i.e. $G$ has $k$ edges and $k$ vertices as shown below). Then we can just number the edges in an increasing order by $1$. Otherwise, if $G$ is a tree, then also we can pick a path between the leaves of the tree and label the edges in a increasing order and also the subtrees in a similar increasing by $1$ order. It is easy to see that this works.
lelouchvigeo
02.01.2024 10:50
Consider a path. Label all the edges on the path as consecutive numbers. The process will be over when there is a vertice with degree one or there is a vertice whose edges are already labeled .Therefore for all the vertices in our path our condition will be satisfied. Now consider a vertex who wasn't in this path. It will have no edges labelled. So we start the same process again. Then after repeating the process a few more times we will be done.
renrenthehamster
09.08.2024 06:49
If you are familiar with depth first search (DFS) algorithm, simply perform depth-first search starting at any chosen root $v$ and label the edges in the order of discovery. Other than the root $v$, all other vertices with at least degree 2 must have a pair of consecutive integer labelled edges (when you first enter the vertex by an edge, you still have at least an undiscovered edge and DFS forces you to immediately discover one of your undiscovered edge). The exception to this argument is the root, but the root has an edge with label 1. By the way this is why you need the graph to be connected - so that you only have 1 root to deal with.
IMD2
10.08.2024 06:53
thdnder wrote: An inductive solution. Let $G = (V,E)$. We induct on $|V|$, assuming $|V| \geq 3$. Assume the problem statement is true on all connected graph with the number of vertices less than $|V|$. Since $G$ is connected, let $T$ be the spanning tree of $G$. Let $v$ be a leaf of $T$. Then $G-v$ is still connected, so by the induction hypothesis, we can label the edges of $G-v$ satisfying the problem condition. Let $\deg v = s$. Then if $s \geq 2$, $\gcd(k, k-1, \dots, k-s+1) = 1$ so labeling the remaining edges in arbitrary order will be satisfying the condition. Thus we're done. What if the vertex $s$ is connected to goes from degree 1 to degree 2 when you include $s$?