Graph Theory Problem For integers n 2 let Gn be a complete

Graph Theory Problem

For integers n > 2, let G_n be a complete graph on n vertices such that each vertex is labeled by a distinct number 1, 2, 3, ..., n, and each edge is labeled by the sum of its endpoint labels. Let f(G_n) be the minimum sum of edge labels in any path that touches every vertex in G_n exactly once. How many values of n satisfy f(G_n) 2013 (mod n)?

Solution

in the path every vertex will have degree two except the end vertices. So we every vertex (number) will be summed twice except the end point vertices

So we will have maximum number vertices (n and n-1) at the end points to make the sum minimum

and the sum would be

f(G_n) = 2*(1+2+....+n-2) + n-1 + n = 2*(n-1)(n-2)/2 + n-1 + n = (n-1)^2 + n = n^2 - n + 1

n^2 - n +1 = 2013 (mod n )

so

n^2 - n -2012 = k*n for some k

so we want

n(n-k-1) = 2012

2012= 503 * 2 * 2

so we can have n =503 k = 498

or n = 1006 , k = 1003

n = 2012 , k = 2010

three choices