On Sep 20, 7:42 am, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> 2N-2 clearly suffices: Consider a tree whose N-1 edges
> are traversed once toward the root and once away. I have a
> sneaking suspicion that 2N-2 is *the* answer, but I also have
> a nagging worry that a cleverer arrangement might exist.
Let A be a solution for N citizens. If we can always construct a
solution for (N-1) citizens by removing two edges from A, then
Sosman's Conjecture will follow by induction.
Pick any citizen C whose first call is out-going. We will derive
a solution A', with at least two fewer edges than A,
for the (N-1) citizens other than C. We delete C's
first call (always out-going by choice of C); and his
first in-coming call (label the caller D).
We now need only to reroute C's remaining calls
to ensure the same gossip criterion is met.
Replace all of C's out-going calls (except first call which
was simply deleted) by calls from D.
The only complication that can arise is if C received two or
more in-coming calls, i.e. calls from E, F, etc. after his
call from D. Replace each of these calls (E-->C, F-->C, etc.)
with calls to D (E-->D, F-->D, etc.)
This works, no?