Nocycleland is a country with $500$ cities and $2013$ two-way roads, each one of them connecting two cities. A city $A$ neighbors $B$ if there is one road that connects them, and a city $A$ quasi-neighbors $B$ if there is a city $C$ such that $A$ neighbors $C$ and $C$ neighbors $B$. It is known that in Nocycleland, there are no pair of cities connected directly with more than one road, and there are no four cities $A$, $B$, $C$ and $D$ such that $A$ neighbors $B$, $B$ neighbors $C$, $C$ neighbors $D$, and $D$ neighbors $A$. Show that there is at least one city that quasi-neighbors at least $57$ other cities.
Problem
Source:
Tags: combinatorics proposed, combinatorics
JBL
02.09.2014 01:29
Let $500=N$ and $2013=E$. For a vertex $v$, let $d(v)$ be the number of neighbors of $v$ and let $d_2(v)$ be the number of quasi-neighbors of $v$. The condition that there is no 4-cycle implies that if $A$ and $B$ are quasi-neighbors then there is exactly one choice of $C$ adjacent to both. Thus $d_2(v) =\sum_{w\sim v} (d(w)-1)$, where the relation $\sim$ is adjacency. It follows that \begin{align*}\sum_v d_2(v)&=\sum_v\sum_{w\sim v} (d(w)-1)\\&=\sum_w d(w)(d(w)-1).\end{align*} Obviously $\sum d(w)=2 E$. Therefore $\sum d(w)^2\geq (2E)^2/N$ and so $\sum d_2(v)\geq (2E)^2/N -2E$. Thus the average value of $d_2(v)$ is at least $(2E)^2/N^2 -2E/N$. Plugging in the given values for $N,E$ shows that this number is larger than $56$; thus, for some vertex $v$ it must be at least $57$.
parmenides51
16.09.2021 10:36
solved from here and here
mavropnevma wrote:
Solution 3. So we are given a simple (no loops, no parallel edges) graph $G(V,E)$ with $|V|=n=500$ vertices and $|E|=m=2013$ edges, which contains no $4$-cycle (whence the name of the country!). Denote by $N(u)$ the set of the neighbours of $u$. Then, if $v,w \in N(u)$, $v\neq w$, it follows $N(v)\cap N(w) = \{u\}$, otherwise, if there existed $x \in (N(v)\cap N(w)) \setminus \{u\}$, we would have the $4$-cycle $uvxwu$. Denote by $n(u)$ the number of quasi-neighbours of $u$; it means $\displaystyle n(u) = \sum_{v\in N(u)} (\deg(v) - 1)$, so $\displaystyle \sum_{u\in V} n(u) = \sum_{u\in V} \sum_{v\in N(u)} (\deg(v) - 1)$. But each term $(\deg(v) - 1)$ in that sum appears $\deg(v)$ times, so $\displaystyle \sum_{u\in V} n(u) = \sum_{v\in V} \deg(v)(\deg(v) - 1) \geq n \left (\dfrac {1} {n} \sum_{v\in V} \deg(v)\right ) \left ( \dfrac {1} {n} \sum_{v\in V} \deg(v) - 1 \right )$, by Jensen (or any other trivial inequality). Remember the first relation learned for simple graphs, namely $\displaystyle \sum_{v\in V} \deg(v) = 2m$, to get $\displaystyle \sum_{u\in V} n(u) \geq n \cdot \dfrac {2m} {n} \left ( \dfrac {2m} {n} - 1 \right )$. This means for (at least) one vertex $u$ we have $n(u) \geq \left \lceil \dfrac {2m} {n} \left ( \dfrac {2m} {n} - 1 \right ) \right \rceil$, which for our numerical case is computed to be equal to $\left \lceil \dfrac {8052} {1000} \cdot \dfrac {7052} {1000} \right \rceil = 57$. A classical piece of double-counting.
mavropnevma wrote:
Alternative Solution 3. Under the same notations as above, we can also reason in this (almost equivalent) way. For each vertex $v\in V$ there exist $\dfrac {1} {2}\deg(v)(deg(v)-1)$ unordered pairs of quasi-neighbours among its neighbours. No such pair is double counted over $G$, since there are no $4$-cycles. On the other hand, the total number $N$ of unordered pairs of quasi-neighbours is clearly equal to $N = \dfrac {1} {2} \sum_{u\in V} n(u)$. Therefore $\sum_{u\in V} n(u) = 2N = \sum_{v\in V} \deg(v)(deg(v)-1)$, and we have reached the same relation as above.