Let return the maximum possible sum (of values of edges) of an Euler path of a graph with vertices (numbered 1 to and each edge numbered with the sum of vertices it joins).
Then for how many does :
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
If n is odd, then every vertex of the complete graph K n has even valency, and hence an Eulerian cycle is possible. Clearly, using the complete graph will give the maximum edge sum. Thus every vertex contributes to the value of n − 1 edges, and hence f ( n ) = ( n − 1 ) i = 1 ∑ n i = 2 1 n ( n + 1 ) ( n − 1 ) Thus f ( n ) ≡ 0 ( m o d n ) , so if f ( n ) ≡ 2 0 1 3 ( m o d n ) then 2 0 1 3 ≡ 0 ( m o d n ) , and hence n divides 2 0 1 3 . Since 2 0 1 3 = 3 × 1 1 × 6 1 , there are 2 3 = 8 divisors of 2 0 1 3 , and all of these are odd.
If n = 2 , then K 2 possesses an Euler path, and f ( 2 ) = 3 ≡ 2 0 1 3 ( m o d 2 ) .
If n ≥ 4 is even, then all the vertices of the complete graph K n have odd valency. To be able to have an Euler path, we need to remove edges from K n so that n − 2 vertices have their valencies made even, and we wish to do this in a way which minimizes the reduction to the edge sum. We do this by removing one edge from each of the vertices 1 , 2 , . . . , n − 2 ; since n is even, this can be done without any repetition of vertices, for example by removing ( 1 , 2 ) , ( 3 , 4 ) , ..., ( n − 3 , n − 2 ) . This means that f ( n ) = 2 1 n ( n + 1 ) ( n − 1 ) − 2 1 ( n − 2 ) ( n − 1 ) = 2 1 ( n − 1 ) [ n ( n + 1 ) − ( n − 2 ) ] = 2 1 ( n − 1 ) ( n 2 + 2 ) = 2 1 n 2 ( n − 1 ) + n − 1 and so we note that f ( n ) ≡ − 1 ( m o d n ) this time. If f ( n ) ≡ 2 0 1 3 ( m o d n ) then 2 0 1 3 ≡ − 1 ( m o d n ) , so that n divides 2 0 1 4 = 2 × 1 9 × 5 3 . Thus there are 4 even divisors of 2 0 1 4 , and 3 of these are greater than 2 .
Thus there are 8 + 1 + 3 = 1 2 positive integers n such that f ( n ) ≡ 2 0 1 3 ( m o d n ) (the eight divisors of 2 0 1 3 , and the four even divisors of 2 0 1 4 ).