Simple 505-Vertex Graph

To count the total number of edges, we can count the number of edges leaving each vertex, and divide the result by $2$ since we counted each edge twice. In this case, for a graph of $M = 2m+1$ vertices where each vertex has $N$ connections, the total number of edges is $E = {(2m+1)N \over 2}$

from which it follows that $N$ must be even. Also , clearly we must have $n < m$ .

Now we will show that every possible value $2n$ has an associated graph.

Label the vertices $V_0, V_1, V_2, ..., V_{2m}$ and let $G_n$ be the graph with these vertices such that vertices $V_i$ and $V_j$ are connected by an edge if and only if $i - j \equiv x \mod M$ or $i - j \equiv -x \mod M$ for some integer $0 \lt x \le n$ .

It follows directly from this definition that any particular vertex $V_a$ is connected to all vertices $V_b$ such that $b \equiv a \pm x \mod M$ for all $0 \lt x \le n$ .

These possible values of $b$ are all distinct because $2n < M$ . Therefore $V_a$ is connected to exactly $2n$ vertices, and $G_n$ is a graph where all vertices are connected to exactly $2n$ others.

Since $n$ can range from $0$ to $m$ in this proof, and if $M = 505$ then $m = 252$ , there are $\boxed{253}$ possible values of $n$ .

It is known that a simple regular graph of degree $N$ and number of vertices $v$ will exist iff $v \geq N+1$ and $vn \equiv 0 \pmod{2}$ . Here we have $v=505$ . The necessary conditions are:

• $505N \equiv 0 \pmod{2} \implies N \equiv 2 \pmod{2}$
• $N \leq 504$

There are $\left \lfloor \frac{504}{2} \right \rfloor + 1= \boxed{253}$ possible values of $N$ .

Let's start to analyze simpler settings. 505 is an odd number, so we'll consider only settings with an odd number of vertice.

• 1 vertice: this is the simplest graph, N can only be 0 (no edges). N=0, obviously, is a valid solution for all graphs.

• 3 vertices: N could be 0, 1, 2. N=0 is acceptable. N=1 is not an acceptable solution; indeed only an edge (N=1) means to join pair of vertices, but the vertices are odd, therefore there will always be one of them unpaired. N=2, in all graphs, means to join sequentially the vertices and to build a shape; so it's always possible. Concluding for 3 vertices N can be 0 and 2.

• 5 vertices: N could be 0, 1, 2, 3, 4. For the above reasons 0 is acceptable, 1 is unacceptable, 2 is acceptable. N=3 is unacceptable indeed there will always be a vertice with one more or less edge then 3. N=4 is acceptable and it means join all vertices together. Whit n vertices it's always possible to use n-1 edges, joining all vertices together; so N=n-1 it' always acceptable. So for 5 vertices N can be 0, 2 and 4

• Trying more with 7 vertices you can find that N can be 0, 2, 4 and 6.

We can conclude for induction that N with n (where n is an odd integer) vertices can always be an even number between 0 and n-1 including. So all possible N are (n+1)/2 and for 505 vertices the answer is 253.

$N$ must be even for there are $505N / 2$ edges. We show that every possible even $N$ actually occurs. The construction is as follows -- arange vertices in a circle. Connect every vertex to a vertex with a distance less or equal than $N/2$ (there are precisely $N$ such neighbors). This defines a graph because the distance function is symmetric. We are done and so the answer is $(505 + 1) / 2\ = {\bf 253}$ (don't forget the disconnected graph with no edges!).

According to Erdős–Gallai theorem ( http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem ) N satisfies the condition if and only if N is even. Even numbers between 0 (inclusive) and 505 are 253.

Well if there are 505 vertices, clearly the number of connections is 505N/2, which must be an integer. This occurs when N=0,2,4,...504 or 253 values of N

A graph must have even number of odd vertices.

The proof of this is the same as the first worked example here .

Since it is given that the number of vertices is 505(which is undeniably odd :P) and each vertices have same number of edges protruding from it,the number of edges ie $N$ must be even. The number of even numbers upto 505 is 253,and thus we arrive at the answer.

We start by counting the total edges. $505$ vertices with $N$ edges per vertex means $505N$ edges, but since each edge is counted twice from the two vertices it connects, we divide by $2$ to get $\dfrac{505N}{2}$ edges. Therefore $N$ is even. Since $0\le N\le 504$ , there are $\boxed{253}$ possibilities for $N$ .