by egxa, Apr 27, 2025, 1:57 PM
There are

cities in a country, where

is an integer. Some pairs of cities are connected by direct (two-way) flights. For two cities

and

we define:

A

between

and

as a sequence of distinct cities
,
, such that there are direct flights between

and

for every
;

A

between

and

as a path between

and

such that no other path between

and

has more cities;

A

between

and

as a path between

and

such that no other path between

and

has fewer cities.
Assume that for any pair of cities

and

in the country, there exist a long path and a short path between them that have no cities in common (except

and
). Let

be the total number of pairs of cities in the country that are connected by direct flights. In terms of
, find all possible values
Proposed by David-Andrei Anghel, Romania.
This post has been edited 6 times. Last edited by egxa, Apr 27, 2025, 10:59 PM