Excellent problem.
Note that we may simply let the regular polygon be a complete graph on n vertices; let the vertices be A_1,A_2,\cdots, A_n. Let f(A_iA_j) return the label of the edge connecting A_i and A_j.
a) We claim that r=n-1\ \forall\ n. First, we show that we cannot have r\geq n for any n. Assume this is true for n=3,4,\cdots, k-1. Assume for the sake of contradiction that it is also possible for n=k. Then by the first restriction, there must exist an edge with label k, WLOG let it be A_{k-1}A_k.
Obviously the claim holds for n=3.
Then for 1\leq i\leq k-2, exactly one of j\in\{k-1,k\} must satisfy f(A_iA_j)=k by the second condition. Let X_1,X_2 be the set of indices such that j=k,k-1 respectively. Let x_1=|X_1|,x_2=|X_2| and WLOG x_1\geq x_2.
Case 1: x_2=0. Then f(A_{k-1}A_i)\neq k\ \forall\ i, and no two i,j\in X_1 can have f(A_iA_j)=k without violating the second condition (we get a triangle with equal labels on all sides). Hence we may ignore A_k, since all other edges (which aren't connected to A_k ) must have label less than k. Hence we must distribute labels from 1,2,\cdots, k-1 to the remaining edges formed by A_1,A_2,\cdots, A_{k-1}, but this is impossible by the induction hypothesis.
Case 2: x_2\neq 0.
Claim: If this case is doable, it is always doable by letting f(A_iA_j)=k for all i\in X_1,j\in X_2.
Proof: This is a very natural claim. Note that since no edge with both vertices in one of X_1,X_2 can have label k. Hence by replacing any edge between the two sets with label not k, we can replace the label with k without causing a contradiction (no triangles are formed, and the other conditions are easy to check).
Now it suffices to label X_1\cup \{n-1\} and X_2\cup \{n\}, but each of these can give us less than x_1, x_2 colors, meaning their union gives us less than n colors. Hence we may conclude r<n.
We inductively construct a graph for r=n-1. For k=3, start with a triangle A_1A_2A_3 with f(A_1A_2)=f(A_2A_3)=3, f(A_3A_1)=1. Then we can use induction to show that the perimeter of a valid configuration with k-1 vertices has labels 1,2,3,\cdots,k-2,k-1,k-1. Now increment the label of every edge in the initial config; this gives us every label in \{2,k+1\} by induction hypothesis. Then if the points are indexed so that f(A_1A_2)=2,f(A_2A_3)=3,\cdots, f(A_{n-2}A_{n-1})=k-1, f(A_{n-1}A_n)=f(A_nA_1)=k, let f(A_{k+1}A_1)=1,f(A_{k+1}A_k)=2,f(A_{k+1}A_{k-1})=3, etc. It is easy to verify that this is indeed valid, although the details are quite tedious.
b) Intuitively, it should be obvious that each valid configuration should be unique up to symmetry. Indeed, we claim that there can only be 1 edge with label 1. Assume otherwise; let a valid n-graph have AB and CD with label 1. (we cannot have f(AB)=1 and f(AC)=1 without violating the second condition). Then removing point A gives a valid configuration with n-1 vertices, since the first condition is obviously satisfied (If f(AX)=f(BX)\ \forall\ X) and the second follows quite easily. But this gives a valid configuration with n-1 vertices with r=n-1, contradicting the result of a).
Now if g(x) is the number of ways to label with x vertices, the proof of the above claim shows that there exists a bijection between each valid x-graph with f(A_iA_j)=1 and a valid x-1-graph, i.e. g(x)=\binom{x}{2}g(x-1) since there are \binom{x}{2} ways to choose the side with label 1. Hence by induction, it follows that \boxed{g(x)=\dfrac{x!(x-1)!}{2^{x-1}}}.