Consider the graph on $1000$ vertices $v_1, v_2, ...v_{1000}$ such that for all $1 \le i < j  \le 1000$, $v_i$ is connected to $v_j$ if and only if $i$ divides $j$. Determine the minimum number of colors that must be used to color the vertices of this graph such that no two vertices sharing an edge are the same color.
1. **Understanding the Graph Construction**:
   - We have a graph with vertices \( v_1, v_2, \ldots, v_{1000} \).
   - An edge exists between \( v_i \) and \( v_j \) if and only if \( i \) divides \( j \) (i.e., \( i \mid j \)).

2. **Identifying Cliques**:
   - A clique is a subset of vertices such that every two distinct vertices are adjacent.
   - Consider the vertices \( v_1, v_2, v_4, \ldots, v_{512} \). These vertices form a clique because:
     - \( 1 \mid 2 \), \( 1 \mid 4 \), \( 2 \mid 4 \), and so on.
     - Each vertex \( v_{2^k} \) (where \( k \) ranges from 0 to 9) divides \( v_{2^m} \) for \( m > k \).

3. **Clique Size**:
   - The vertices \( v_1, v_2, v_4, \ldots, v_{512} \) form a clique of size 10 because \( 2^9 = 512 \) and \( 2^{10} = 1024 \) which is greater than 1000.
   - Therefore, we need at least 10 colors to color this clique since each vertex in a clique must have a unique color.

4. **Coloring Strategy**:
   - We color the vertices based on the number of prime factors in their prime factorization (counted with multiplicity).
   - For example, \( 12 = 2^2 \times 3 \) has 3 prime factors (2, 2, and 3).

5. **Prime Factorization and Coloring**:
   - Since \( 1000 < 2^{10} \), each number \( v_i \) (where \( 1 \leq i \leq 1000 \)) has at most 9 prime factors.
   - Therefore, we need 10 colors to ensure that no two adjacent vertices (where one divides the other) share the same color.

6. **Verification**:
   - If \( i \mid j \), then the number of prime factors of \( i \) is less than or equal to the number of prime factors of \( j \).
   - Thus, by coloring vertices based on the number of prime factors, we ensure that adjacent vertices have different colors.

Conclusion:
\[
\boxed{10}
\]