Nice problem. It's secretly geometry however. The problem essentially states that the graph of all suburban cities is connected. We shall first look at the geometry - we have the following claim: Claim. \[\left\vert\{X\mid N(X)=Y\}\right\vert\leq 5\]Proof. Suppose that it was at least 6, say $X_1,\ldots,X_6$ such that the projections of these points on any circle centered at $Y$ is clockwise. Then, we can note that \[X_jX_{j+1}>X_jY,X_{j+1}Y\]as per the definition of a suburban set. This implies \[\angle X_jYX_{j+1}>\angle X_{j+1}X_jY,\angle X_jX_{j+1}Y\implies\angle X_jYX_{j+1}>\frac\pi3\]Now, adding from $j=1$ to $6$ gives a contradiction, as it gives $2\pi>2\pi$. $\blacksquare$ Now, it's time for the combinatorics part. Suppose there are $k$ suburban cities. Then, as mentioned, the graph on suburban cities is connected, and thus has a degree sum at least $2k-2$. Thus, \[n\geq 6k-(2k-2)=4k+2\]as desired.

naman12 wrote: Nice problem. It's secretly geometry however. The problem essentially states that the graph of all suburban cities is connected. We shall first look at the geometry - we have the following claim: Claim. \[\left\vert\{X\mid N(X)=Y\}\right\vert\leq 5\]Proof. Suppose that it was at least 6, say $X_1,\ldots,X_6$ such that the projections of these points on any circle centered at $Y$ is clockwise. Then, we can note that \[X_jX_{j+1}>X_jY,X_{j+1}Y\]as per the definition of a suburban set. This implies \[\angle X_jYX_{j+1}>\angle X_{j+1}X_jY,\angle X_jX_{j+1}Y\implies\angle X_jYX_{j+1}>\frac\pi3\]Now, adding from $j=1$ to $6$ gives a contradiction, as it gives $2\pi>2\pi$. $\blacksquare$ Now, it's time for the combinatorics part. Suppose there are $k$ suburban cities. Then, as mentioned, the graph on suburban cities is connected, and thus has a degree sum at least $2k-2$. Thus, \[n\geq 6k-(2k-2)=4k+2\]as desired. This might be a dumb question, but how did you get the last inequality?

Take the obvious graph interpretation. Claim: for any vertex $v, \deg(v)\le 5$ Proof. Assume not. Let $k=N(v)$ and $n_1,\cdots, n_5$ be 5 other vertices, in clockwise order with respect to $v$, such that $N(n_i)=v$. WLOG, $n_6=k$ is between $n_5$ and $n_1$ (I translate each point by $-v$ and sort by their argument if they are points in the complex plane) Let $n_7=n_1$. By cosine law, $|N_iN_{i+1}|^2=VN_i^2+VN_{i+1}^2-2VN_i \cdot VN_{i+1} \cos \angle N_iVN_{i+1}$ If $\angle N_iVN_{i+1} \le \frac{\pi}{3}$ then $|N_iN_{i+1}|^2 \le VN_i^2+VN_{i+1}^2 - VN_i \cdot VN_{i+1}$. This $N_iN_{i+1} \le \max\{ VN_i, VN_{i+1} \}$ which is a contradiction as at least one of $N(n_i)=v$. Since $\sum_{i=1}^6 \angle N_iVN_{i+1}=2\pi$, this is impossible by pigeonhole. Claim: the graph is a tree with one double edge. Proof: I first show if the graph has no cycles of length at least 3. Suppose the graph has a cycle, where there is an edge between $v_iv_{i+1}$ for $1\le i \le n$ and indices are taken mod n. If I direct all edges $X\rightarrow N(X)$ then the outdegree of each vertex is 1. If I only consider those edges, $\deg^+(v)\le 1$ for all $v$ in this cycle but $\sum \deg^+(v)=n$ so after orientating the edges this is still a cycle. Suppose $N(V_i)=V_{i+1}$ This implies $|V_iV_{i+1}| > |V_{i-1}V_i|,$ contradiction. Therefore, the graph is a tree with a double edge, since it is connected. It suffices to show that for a set of $n$ suburban cities there are at most $4n+2$ cities total. If I count the 5 neighbors of each suburban city, note $n-1$ edges connect two suburban cities (this is just the number of edges not containing a leaf; consider the tree formed with suburban cities only) Those edges are counted twice in this process so we have at most $4n+1$ edges, so there would be at most $4n+2$ vertices, as needed.

USJL wrote: naman12 wrote: Nice problem. It's secretly geometry however. The problem essentially states that the graph of all suburban cities is connected. We shall first look at the geometry - we have the following claim: Claim. \[\left\vert\{X\mid N(X)=Y\}\right\vert\leq 5\]Proof. Suppose that it was at least 6, say $X_1,\ldots,X_6$ such that the projections of these points on any circle centered at $Y$ is clockwise. Then, we can note that \[X_jX_{j+1}>X_jY,X_{j+1}Y\]as per the definition of a suburban set. This implies \[\angle X_jYX_{j+1}>\angle X_{j+1}X_jY,\angle X_jX_{j+1}Y\implies\angle X_jYX_{j+1}>\frac\pi3\]Now, adding from $j=1$ to $6$ gives a contradiction, as it gives $2\pi>2\pi$. $\blacksquare$ Now, it's time for the combinatorics part. Suppose there are $k$ suburban cities. Then, as mentioned, the graph on suburban cities is connected, and thus has a degree sum at least $2k-2$. Thus, \[n\geq 6k-(2k-2)=4k+2\]as desired. This might be a dumb question, but how did you get the last inequality? I think he got it by counting the two endpoints of each edge containing suburban vertex, where there are at most $k+5k$ of them.

KaiDaMagical336 wrote: Take the obvious graph interpretation. Claim: for any vertex $v, \deg(v)\le 5$ Proof. Assume not. Let $k=N(v)$ and $n_1,\cdots, n_5$ be 5 other vertices, in clockwise order with respect to $v$, such that $N(n_i)=v$. WLOG, $n_6=k$ is between $n_5$ and $n_1$ (I translate each point by $-v$ and sort by their argument if they are points in the complex plane) Let $n_7=n_1$. By cosine law, $|N_iN_{i+1}|^2=VN_i^2+VN_{i+1}^2-2VN_i \cdot VN_{i+1} \cos \angle N_iVN_{i+1}$ If $\angle N_iVN_{i+1} \le \frac{\pi}{3}$ then $|N_iN_{i+1}|^2 \le VN_i^2+VN_{i+1}^2 - VN_i \cdot VN_{i+1}$. This $N_iN_{i+1} \le \max\{ VN_i, VN_{i+1} \}$ which is a contradiction as at least one of $N(n_i)=v$. Since $\sum_{i=1}^6 \angle N_iVN_{i+1}=2\pi$, this is impossible by pigeonhole. Claim: the graph is a tree with one double edge. Proof: I first show if the graph has no cycles of length at least 3. Suppose the graph has a cycle, where there is an edge between $v_iv_{i+1}$ for $1\le i \le n$ and indices are taken mod n. If I direct all edges $X\rightarrow N(X)$ then the outdegree of each vertex is 1. If I only consider those edges, $\deg^+(v)\le 1$ for all $v$ in this cycle but $\sum \deg^+(v)=n$ so after orientating the edges this is still a cycle. Suppose $N(V_i)=V_{i+1}$ This implies $|V_iV_{i+1}| > |V_{i-1}V_i|,$ contradiction. Therefore, the graph is a tree with a double edge, since it is connected. It suffices to show that for a set of $n$ suburban cities there are at most $4n+2$ cities total. If I count the 5 neighbors of each suburban city, note $n-1$ edges connect two suburban cities (this is just the number of edges not containing a leaf; consider the tree formed with suburban cities only) Those edges are counted twice in this process so we have at most $4n+1$ edges, so there would be at most $4n+2$ vertices, as needed. I did not understand the last paragraph. How did you count the 5 neighbours and reach 4n+2?

KaiDaMagical336 wrote: USJL wrote: naman12 wrote: Nice problem. It's secretly geometry however. The problem essentially states that the graph of all suburban cities is connected. We shall first look at the geometry - we have the following claim: Claim. \[\left\vert\{X\mid N(X)=Y\}\right\vert\leq 5\]Proof. Suppose that it was at least 6, say $X_1,\ldots,X_6$ such that the projections of these points on any circle centered at $Y$ is clockwise. Then, we can note that \[X_jX_{j+1}>X_jY,X_{j+1}Y\]as per the definition of a suburban set. This implies \[\angle X_jYX_{j+1}>\angle X_{j+1}X_jY,\angle X_jX_{j+1}Y\implies\angle X_jYX_{j+1}>\frac\pi3\]Now, adding from $j=1$ to $6$ gives a contradiction, as it gives $2\pi>2\pi$. $\blacksquare$ Now, it's time for the combinatorics part. Suppose there are $k$ suburban cities. Then, as mentioned, the graph on suburban cities is connected, and thus has a degree sum at least $2k-2$. Thus, \[n\geq 6k-(2k-2)=4k+2\]as desired. This might be a dumb question, but how did you get the last inequality? I think he got it by counting the two endpoints of each edge containing suburban vertex, where there are at most $k+5k$ of them. I thought by this we only get $k\geq n/5$?

Oops here's how I got it (too lazy to write up rigorously, I'm probably also trolling here): For a city $X$, the number of non-suburban cities is $5-d(X)$, where $d(X)$ is the degree. Thus, summing, we have a total of at least \[5k-\sum_{x\in S}d(X)\geq 5k-(2k-2)=3k+2\]non-suburban cities, so at least $4k-2$ cities...just kidding I flipped a sign *sigh*. I hate combo. To remedy this, we show there is no cycle of degree greater than 2. This is actually extremely simple - the two closest points must point to each other, and as the total degree (directed) is $2k$, the maximum (undirected) degree is $2k-2$, so we must have a tree. Thus, \[\sum_{x\in S}d(X)=2k-2\]and the rest follows.

SerdarBozdag wrote: KaiDaMagical336 wrote: Take the obvious graph interpretation. Claim: for any vertex $v, \deg(v)\le 5$ Proof. Assume not. Let $k=N(v)$ and $n_1,\cdots, n_5$ be 5 other vertices, in clockwise order with respect to $v$, such that $N(n_i)=v$. WLOG, $n_6=k$ is between $n_5$ and $n_1$ (I translate each point by $-v$ and sort by their argument if they are points in the complex plane) Let $n_7=n_1$. By cosine law, $|N_iN_{i+1}|^2=VN_i^2+VN_{i+1}^2-2VN_i \cdot VN_{i+1} \cos \angle N_iVN_{i+1}$ If $\angle N_iVN_{i+1} \le \frac{\pi}{3}$ then $|N_iN_{i+1}|^2 \le VN_i^2+VN_{i+1}^2 - VN_i \cdot VN_{i+1}$. This $N_iN_{i+1} \le \max\{ VN_i, VN_{i+1} \}$ which is a contradiction as at least one of $N(n_i)=v$. Since $\sum_{i=1}^6 \angle N_iVN_{i+1}=2\pi$, this is impossible by pigeonhole. Claim: the graph is a tree with one double edge. Proof: I first show if the graph has no cycles of length at least 3. Suppose the graph has a cycle, where there is an edge between $v_iv_{i+1}$ for $1\le i \le n$ and indices are taken mod n. If I direct all edges $X\rightarrow N(X)$ then the outdegree of each vertex is 1. If I only consider those edges, $\deg^+(v)\le 1$ for all $v$ in this cycle but $\sum \deg^+(v)=n$ so after orientating the edges this is still a cycle. Suppose $N(V_i)=V_{i+1}$ This implies $|V_iV_{i+1}| > |V_{i-1}V_i|,$ contradiction. Therefore, the graph is a tree with a double edge, since it is connected. It suffices to show that for a set of $n$ suburban cities there are at most $4n+2$ cities total. If I count the 5 neighbors of each suburban city, note $n-1$ edges connect two suburban cities (this is just the number of edges not containing a leaf; consider the tree formed with suburban cities only) Those edges are counted twice in this process so we have at most $4n+1$ edges, so there would be at most $4n+2$ vertices, as needed. I did not understand the last paragraph. How did you count the 5 neighbours and reach 4n+2? Thanks for reaching out! Consider the $\le 5$ edges with an endpoint as a suburban city. If an edge connects two suburban cities, it is counted twice; once for each suburban city. There are $n-1$ such edges because the edges between suburban cities form a tree (the set of suburban cities is the set of non-leaves). On the other hand, an edge between a suburban city and a leaf is counted once. If $M$ is the number of such edges then $M+2(n-1)\le 5n$. Therefore there are $\le 5n-2(n-1)$ edges between a suburban city and a leaf. In total, there are at most $5n-2(n-1)+(n-1)=4n+1$ edges. Since the number of edges in a tree is one less than the number of vertices, there would be at most $4n+2$ vertices.

naman12 wrote: Oops here's how I got it (too lazy to write up rigorously, I'm probably also trolling here): For a city $X$, the number of non-suburban cities is $5-d(X)$, where $d(X)$ is the degree. Thus, summing, we have a total of at least \[5k-\sum_{x\in S}d(X)\geq 5k-(2k-2)=3k+2\]non-suburban cities, so at least $4k-2$ cities...just kidding I flipped a sign *sigh*. I hate combo. To remedy this, we show there is no cycle of degree greater than 2. This is actually extremely simple - the two closest points must point to each other, and as the total degree (directed) is $2k$, the maximum (undirected) degree is $2k-2$, so we must have a tree. Thus, \[\sum_{x\in S}d(X)=2k-2\]and the rest follows. I think one thing that you are also missing is that you showed for each $X$ there are at most $5$ $Y$'s such that $N(Y)=X$, but in the proof you use that each vertex has degree at most $5$. This assertion is equivalent to that for each $X$ there are at most $5$ $Y$'s such that $N(Y)=X$ OR $N(X)=Y$ (or both). Those two are different.

Solved with Elliott Liu, Isaac Zhu, Jeffrey Chen, Kevin Wu, Luke Robitaille, and Raymond Feng. First, an observation: Claim 1: There is exactly one bidirectional edge. Proof. The shortest edge must be bidirectional, and if there is another, then the graph cannot be connected. \(\blacksquare\) Now the main claim: Claim 2: All vertices have indegree at most 5. Proof. If \(V\) is the closest city to \(V_1\), \(V_2\), \ldots, \(V_6\) in counterclockwise order, then since \(\angle V_1VV_2+\cdots+\angle V_6VV_1=360^\circ\), for some index \(i\) we have \(\angle V_iVV_{i+1}\le60^\circ\). Then \(V_iV_{i+1}\) is shorter than either \(VV_i\) or \(VV_{i+1}\), contradiction. \(\blacksquare\) To strengthen the above bound: Claim 3: At most two vertices have indegree 5. Proof. We will show a vertex with indegree 5 must be incident to the shortest edge. Otherwise there are six ``short'' edges incident to this vertex, so repeat the proof of Claim 2. \(\blacksquare\) Finally there are \(n\) edges, so if there are \(s\) suburban cities, then \[n\le10+4(s-2)\implies s\ge\frac{n-2}4,\]as desired.

Draw a directed edge from $X$ to $N(X)$ for all $X$, so every vertex has outdegree $1$. We will alternate between this digraph view and the original undirected formulation; which "mode" we are in should be clear by context. Claim: There exists exactly one repeated edge. Proof: Obviously the two closest points have a repeated edge between them. If we (temporarily) replace this by a single edge, the result is a connected graph on $n$ vertices with $n-1$ edges, which is a tree. In particular, it cannot have any other repeated edges. $\blacksquare$ This sets up the main claim. Claim: No vertex has $6$ (or more) vertices adjacent to it. Proof: If we found six points $P_1,\ldots,P_6$ in clockwise order adjacent to a point $X$, the minimal angle $\angle P_iXP_{i+1}$ is at most $60^\circ$, so Law of Cosines gives $$P_iP_{i+1}^2\leq XP_i^2+XP_{i+1}^2-XP_i\cdot XP_{i+1} \leq \max\{XP_i^2,XP_{i+1}^2\}.$$Equality only holds when $\angle P_iXP_{i+1}=60^\circ$ and $XP_i=XP_{i+1}$. WLOG suppose that $XP_i\geq XP_{i+1}$ and equality doesn't hold. If $P_i \to X$ is an edge we obtain an immediate contradiction, since $P_iX>P_iP_{i+1}$. If $X \to P_i$ is an edge, we get a contradiction since $P_i$ is no longer the unique closest point to $X$. Thus in order to not obtain a contradiction, we need equality to hold. Then the minimal angle is $60^\circ$, so every angle is $60^\circ$. Applying this argument to every angle $\angle P_jXP_{j+1}$ then gets us a contradiction when $X \to P_j$ is an edge. $\blacksquare$ Thus every vertex has indegree at most $4$, except for the two vertices sharing the repeated edge which have indegree at most $5$, since no other edges are repeated. On the other hand, the sum of indegrees equals the sum of outdegrees, which is $1$. Thus we need at least $\tfrac{n-2}{4}$ vertices to have positive indegree. These are precisely the suburban cities, so we're done. $\blacksquare$