Let $G$ be a graph with $n$ vertices and $k - 1$ edges. Let $p_1, \dots, p_{k - 1}$ be distinct primes; assign one prime to each edge. On each vertex, write the product of the numbers on the edges adjacent to it. Relabel vertices with 1 with distinct primes not dividing any of the other numbers involved. The valid gcds are exactly $1, p_1, \dots, p_{k - 1}$, so the $n$ positive integers on the vertices are as desired.

Weak induction on $k$. For $k=1$ take all elements as distinct primes. Suppose the sentence below is true for $k=j<n(n-1)/2$. It means there is a set $A$;$|A|=n$ and If $B$ is the set of distinct "$gcd's$" between all pairs of $A$, $B$ has exactly $j$ distinct elements.Thus, by pigeonhole principle, there exist two distinct (not necessarily disjoint) pairs of $A$ $(a,b);(c,d)/gcd(a,b)=gcd(c,d)=g$.Then, to create our desired set $A'$; (where G is the set of distinct $gcd$ betweeen all pairs of $A'$) such that $|G|=j+1$, repeat all elements of $A$, except $a$ and $b$. Replace $a$ by $p.a$ and b by $p.b$, where $p$ is a prime that does not divide any element of $A$ .Notice that $|G|=|B|+1$(the new element is $p.g$). The result follows by induction ∎