Product of the edges is distinct We have a complete graph with $n\geq 3$ vertices. Show that we can label the edges with $1,2$, or $3$ so that the product of the edges is distinct at every vertex. For $n=3$ this is obvious. For larger $n$ I'm not sure how to apply the induction hypothesis, as we don't know what the distinct products are.
 A: Here is one possible way to do the induction. (The key idea is that, even if we don't know what the distinct products are, by labeling edges judiciously, we can always ensure that either none of the products is a power of 2 or none of the products is a power of 3). 
You've already noted that the base case for $n=3$ is obvious (use all three labels). We will also need the following base case for $n=4$: take the base case for $n=3$, add a fourth vertex, and connect it to all the existing vertices with edges labelled '2'. Then note that the products at the vertices are now 4, 6, 12, and 8. 
Note that these products are a) distinct, and b) contain no power of 3. We will now prove a stronger claim by induction: namely, for each $n \geq 4$, there exists a complete graph on $n$ vertices with labels in $\{1, 2, 3\}$ such that the vertex products are distinct and either don't include a power of $2$ or don't include a power of $3$.
We've shown the base case for $n=4$, so it remains to show the inductive step. Assume we have a graph on $n$ vertices whose vertex products don't contain a power of $3$. Then, by adding an $n+1$th vertex and connecting it to the existing $n$ vertices with edges labelled '3', we multiply each of the existing $n$ vertex products by 3. Since they were originally distinct, they are still distinct; furthermore, since they are now divisible by 3, they cannot be powers of 2, and since they were originally not powers of 3, they cannot be powers of 3. Our new vertex has the product $3^n$ and is a power of 3, so it does not equal the product at any other vertex (and is not a power of 2). 
A similar argument works for the case where the vertex products don't contain a power of 2 (namely, connect a new vertex to all vertices with edges labelled '2'). This completes the proof.
A: Hint: given a complete graph on $n$ nodes, we can construct a complete graph on $n + 1$ nodes by adding one more node and connecting it to all the others.
