IMC 2009 · Day 1 · P3

Let us define the simple, undirected graph $G$ so that the vertices of $G$ are the town's residents and the edges of $G$ are the friendships between the residents. Let $V(G) = \{v_1, v_2, \dots, v_n\}$ denote the vertices of $G$; $a_i$ is degree of $v_i$ for every $i$. Let $E(G)$ denote the edges of $G$. In this terminology, the problem asks us to describe the length $k$ of the shortest cycle in $G$.

Let us count the walks of length 2 in $G$, that is, the ordered triples $(v_i, v_j, v_l)$ of vertices with $v_i v_j, v_j v_l \in E(G)$ ($i = l$ being allowed). For a given $j$ the number is obviously $a_j^2$, therefore the total number is $\sum_{i=1}^{n} a_i^2 = n^2 - n$.

Now we show that there is an injection $f$ from the set of ordered pairs of distinct vertices to the set of these walks. For $v_i v_j \notin E(G)$, let $f(v_i, v_j) = (v_i, v_l, v_j)$ with arbitrary $l$ such that $v_i v_l, v_l v_j \in E(G)$. For $v_i v_j \in E(G)$, let $f(v_i, v_j) = (v_i, v_j, v_i)$. $f$ is an injection since for $i = l$, $(v_i, v_j, v_l)$ can only be the image of $(v_i, v_j)$, and for $i \ne l$, it can only be the image of $(v_i, v_l)$.

Since the number of ordered pairs of distinct vertices is $n^2 - n$, $\sum_{i=1}^{n} a_i^2 \ge n^2 - n$. Equality holds iff $f$ is surjective, that is, iff there is exactly one $l$ with $v_i v_l, v_l v_j \in E(G)$ for every $i, j$ with $v_i v_j \notin E(G)$ and there is no such $l$ for any $i, j$ with $v_i v_j \in E(G)$. In other words, iff $G$ contains neither $C_3$ nor $C_4$ (cycles of length 3 or 4), that is, $G$ is either a forest (a cycle-free graph) or the length of its shortest cycle is at least 5.

It is easy to check that if every two vertices of a forest are connected by a path of length at most 2, then the forest is a star (one vertex is connected to all others by an edge). But $G$ has $n$ vertices, and none of them has degree $n - 1$. Hence $G$ is not forest, so it has cycles. On the other hand, if the length of a cycle $C$ of $G$ is at least 6 then it has two vertices such that both arcs of $C$ connecting them are longer than 2. Hence there is a path connecting them that is shorter than both arcs. Replacing one of the arcs by this path, we have a closed walk shorter than $C$. Therefore length of the shortest cycle is 5.

Finally, we must note that there is at least one $G$ with the prescribed properties – e.g. the cycle $C_5$ itself satisfies the conditions. Thus 5 is the sole possible value of $k$.