%Article: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%Author:  Brenda Baker, Robert Shostak;
%Title:   Gossips and Telephones
\vsize=25cm
\parskip=2pt
\font\sc=cmcsc10
\def\f{f}  % minimum number of calls needed

\centerline{{\bf Gossips and Telephones}%
\footnote{*}{Received 3 September 1971}}
\centerline{{\sc Brenda Baker} and {\sc Robert Shostak}\footnote{\dag}%
{Both authors are NSF-Pre-Doctoral Fellows at Harward University}}
\centerline{Discrete Mathematics 2 (1972) 191--193}

The following problem has circulated lately among mathematicians.
Other solutions have been given independently by R. T. Bumby and
by A. Hajnal, E. C. Milner and E. Szemer\'edi.
\smallskip

{\bf The problem.}
There are n ladies, and each of them knows some item of gossip
not known to the others. They communicate by telephone, and
whenever one lady calls another, they tell each other all that
they know at that time. How many calls are required before each
gossip knows everything?
\smallskip

{\bf Answer.}
Let $\f(n)$ be the minimum number of calls needed for n people.
It is easily shown that $\f(1) = 0$, $\f(2) = 1$, $\f(3) = 3$ and $\f(4) = 4$.
For $n>4$, $2n-4$ calls are sufficient according to the following procedure:
one of four ``chief'' gossips first calls each of the remaining $n-4$ gossips,
then the four learn each other's (and hence everyone's) information in 4
calls (as $\f(4) = 4$), and finally one of the four chiefs calls each of the
other $n-4$ gossips.
\smallskip

{\bf Theorem.} \quad $\f(n) = 2n - 4$ for $n > 4$.
\smallskip

{\bf Proof.} Suppose to the contrary that for some $n>4$, $\f(n) \le 2n-5$.
Let $m$ be the least such $n$ and let $S$ be any calling arrangement among
$m$ gossips requiring at most $2m-5$ calls. We will obtain a contradiction
based upon the following lemma.
\smallskip

{\bf Lemma.} No gossip may hear her own information from another in $S$.
\smallskip

{\bf Proof.} If gossip $G$ can hear her own information in $S$, there is a
sequence of calls $(G-G_1)(G_1-G_2) \cdots (G_r-G)$, listed in temporal order.
By omiting gossip $G$, we obtain from $S$ a new arrangement $T$ of calls among
$m-1$ gossips as follows:

Omit from $S$ calls $(G-G_1)$ and $(G_r-G)$. In addition, for each gossip $P$
who makes a call $(P-G)$ (other than $(G-G_1)$ and $(G_r-G)$ of the above 
sequence) in $S$, let the $G_i$'s transmit $P$'s information in $T$ as follows:
Let $t$ be the least $i$ such that $(G_i-G_{i+1})$ occurs after $(P-G)$ in $S$,
if such a call exists, and $r$ otherwise. Replace $(P-G)$ in $S$ by a call
$(P-G_t)$ in $T$, preserving the temporal ordering of the calls.
The arrangement $T$ will contain at most $2(m-1)-5$ calls and it is easily
verified that all ladies learn all of the gossip in $T$ if they do so in $S$.
The lemma follows by minimality of $m$.
\smallskip

{\bf Conclusion of the proof of the Theorem.} By the Lemma, a call is either
the final call for both parties to the call in $S$ or it is the final call
for neither (for after receiving gossip $B$'s final call, gossip $A$ knows
everything and would violate the Lemma by later calling someone else). Also,
a call is either the initial call for both parties or for neither (otherwise,
if $A$ makes her first call to $B$ after $B$ calls $C$, then information from
$C$ would propagate with $A$'s until it came back to $C$, contradicting the
Lemma).

Thus initial and final calls account for $m$ calls.
(Clearly a call cannot be both initial and final.)
Let the remaining calls be described as intermediate calls and let $I$ be
a graph with $m$ nodes representing gossips and edges representing
intermediate calls. Since there are at most $m-5$ intermediate calls
and since $m-1$ edges are needed for a graph of $m$ nodes to be
connected, the graph $I$ must contain at least five disjoint connected
components. Information from a given gossip $G$ can propagate into only
two components (hers und her initial caller's) before any final calls
are made. Similarly, after the initial calls have been made, information
may be transmitted to her through the calls of only two components
(hers and her final caller's). Thus the calls of at least two components
of intermediate calls play no part in propagating her information or
informing her. For a gossip $G$, let $c(G)$ be the number of calls
which are not used in transmitting information to her or from her.

At least $n-1$ calls are required to inform a given gossip completely
and $n-1$ are required to transmit her information. By the Lemma the
only calls which can do both are those that she herself takes part in
-- otherwise she would hear her information from another. Thus at least
$2n - 2 - v(G)$ calls are required to convey gossip $G$'s information
and inform her, where $v(G)$ is the number of calls in which she
participates. From $2n - 5 \ge 2n - 2 - v(G) + c(G)$ we conclude that
$v(G) \ge 3 + c(G) \ge 3$. Since $v(G) \ge 3$ for each gossip $G$,
every connected component of intermediate calls contains an edge --
otherwise some gossip would make only an initial and a final call.
According to the previous paragraph, the calls of at least two
components are not used in transmitting information to or from $G$.
Hence $c(G) \ge 2$ and $v(G) \ge 5$ for all gossips $G$, resulting in
more than 2n calls altogether.
\smallskip

{\bf Acknowledgments} The authors wish to thank C. L. Liu for his
comments and encouragement, and D. Kleitman for his considerable help
in clarifying the central argument of the proof.
\bigbreak

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%Author:  R. Tijdeman
%Title:   On A Telephone Problem
\vsize=25cm
\font\sc=cmcsc10
\font\eus=eusm10
\def\f{f}  % minimum number of calls needed
\def\Call{\gamma}
%\def\Clistset{{\cal L}}
\def\Clistset{\hbox{\eus L}}
\def\ia{i.a.}
\def\ib{i.b.}

\centerline{\bf On A Telephone Problem}
\centerline{{\sc R. Tijdeman}%
\footnote{*}{This work was supported by Air Force Office of Scientific
Research grant AF-AFOSR-69-1712}
\footnote{}{Received, 16 February 1971}}
\centerline{Nieuw Archief voor Wiskunde (3), XIX, (1971), 188--192}

The problem due to A. Boyd is as follows:
\smallskip

There are n ladies, and each of them knows some item of scandal
which is not known to any of the others. They communicate by telephone, 
and whenever two ladies make a call, they pass on to each other, as
much scandal as they know at that time. How many calls are needed before 
all ladies know all the scandal?
\smallskip

Professor E. A. J. M. Wirsing remarked that this problem is equivalent
to the following one:

A $n \times n$ telephone matrix $(a_{ij})^n_{i,j=1}$ is a matrix of the
following form: $a_{ii} = 1$ for $i = 1, \ldots, n$, there exists a pair
$i_0 \ne j_0$ such that $a_{i_0j_0} = a_{j_0i_0} = 1$ and $a_{ij} = 0$
for all other values of $i$ and $j$. How many $n \times n$ telephone
matrices are needed in order that the product matrix has no entry equal
to zero?

This problem has been solved independently
by A. Hajnal, E. C. Milner and E. Szemer\'edi,
by R. T. Bumby and by the author.
All three solutions are quite different.
In the first mentioned solution 
only the order in which calls are made is changed.
The second uses the idea of a proxy.
The third is done by identification and interchange of ladies
and is given here. I thank Dr. A. J. Jones and Dr. H. L. Montgomery
for the help they have given me in solving the problem and preparing
this paper.
\smallskip

1. Let $\f(n)$ be the number of calls needed for $n$ ladies to know all
the scandal. It is easy to see that $\f(1) = 0$, $\f(2) = 1$, $\f(3)=3$,
$\f(4)=4$. Denoting ladies by $A$, $B$, $C$ and $D$ a solution for $n=4$
is given by $A-B$, $C-D$, $A-C$, $B-D$.
\smallskip

An ordered list of telephone calls is called {\it complete} if after
all calls have been made each person knows all the information.
Let $L$ be a complete list for $n$ ladies $A_1, \ldots, A_n$.
A complete list for these $n$ ladies and a new lady $A_{n+1}$ is
given by the list $A_1 - A_{n+1}, L, A_1 - A_{n+1}$. Hence
$\f(n+1) \le \f(n) + 2$. Since $\f(4)=4$, this implies 
$\f(n) \le 2n - 4$ for all $n \ge 4$. The object is to prove
\smallskip

{\bf Theorem.} \quad $\f(n) = 2n - 4$ for $n \ge 4$.
\smallskip

This seems rather wasteful, since the same result can be 
attained by $2n - 2$ letters (or ``polarized telephones'').
\smallskip

2. Ladies will be given by $A$, $B$, $A_1$, $A_2$ etc., their initial
piece of information by $a$, $b$, $a_1$, $a_2$ etc., lists of telephone
calls by $L$, $L'$, etc. Let $\Clistset_n$ be the set of all complete lists
on $n$ people of length $\f(n)$.

An {\it identification of $A$ and $B$ in a list $L$} is a modification
of the list as follows: Calls between $A$ and $B$ are omitted. $A$ and
$B$ are replaced in the list by a single person denoted by $AB (=BA)$
whose initial information is $ab (=ba)$.

{\it An interchange of $A$ and $B$ (from some point onwards) in a list $L$}
is a modification of $L$ as follows: From the point indicated to the end
of the list the letter $A$ is replaced by the letter $B$ amd vice--versa.

The abbreviations \ib\ and \ia\ will be used to mean 
{\it immediately before} (some call of the list) or
{\it immediately after}, respectively.

To prove the theorem we assume that $N > 4$, that the theorem is true
for $4 \le n < N$ and that $\f(N) < 2N - 4$. We start with some lemmas.
\smallskip

3. {\bf Lemma 1.} If in $L$ the ladies $A$ and $B$ are identified to 
form a list $L'$ then at any point in $L'$ $AB$ knows at least all of
what $A$ and $B$ knew separately at the corresponding point in $L$.
Also, any other person in $L'$ knows at least as much as she knows
at the same time in $L$. In particular the list $L'$ is complete if
$L$ is complete.

{\bf Proof.} By induction on the calls of L.
\smallskip

{\bf Lemma 2.} If $L \in \Clistset_N$ then any two ladies call each
other at most once.

{\bf Proof.} If $A$ and $B$ call each other twice, then identify
$A$ and $B$. Then by Lemma~1 $L'$ is a complete list on $N-1$ ladies,
containing $\f(N) - 2 < 2N - 6 = 2(N-1) - 4$ calls thereby contradicting
the minimality of N.
\smallskip

{\bf Corollary.} For $L \in \Clistset_N$ we may speak of {\it the}
call between $A$ and $B$, which we shall denote by 
$\Call(A,B) (=\Call(B,A))$.
\smallskip

{\bf Lemma 3.} If two ladies in a complete list $L$ are interchanged
at a time when they have precisely the same information, then the new
list $L'$ is also complete.

{\bf Proof.} Clear, since at the time of the interchange the two
ladies are indistinguishable.
\smallskip

{\bf Lemma 4.} If $\Call(A,B)$ is a call of $L \in \Clistset_N$ then
\ib\ $\Call(A,B)$ $A$ and $B$ have no common information.

{\bf Proof.} Suppose $A$ and $B$ have common information $c$. Originally
this information was known only to $C$. Working backwards through the
list $L$ either we can construct two sequences
$$\cases{ 
 & $A = A_0$ learned $c$ from $A_1$, $A_1$ from $A_2, \ldots, A_{k-1}$
from $A_k$, $A_k$ from $D$,\cr
 & $B = B_0$ learned $c$ from $B_1$, $B_1$ from $B_2, \ldots, B_{l-1}$
from $B_l$, $B_l$ from $D$,\cr
} \eqno(1)$$
where by hypothesis $D$ is the only person common to both sequences,
or we construct one sequence
$$\hbox{
$A = A_0$ learned $c$ from $A_1$, $A_1$ from $A_2, \ldots, A_{k-1}$
from $A_k$, $A_k$ from $B = D$
} \eqno(2)$$
(where it may be necessary to interchange $A$ and $B$ from the beginning
of $L$), and $A_i \ne A_j$ $(0 \le i < j \le k)$.

If (1) holds we may, without loss of generality, assume that 
$\Call(A_k,D)$ occurs before $\Call(B_l,D)$. Interchange $B_l$ and $D$
\ia\ $\Call(B_l,D)$, subsequently interchange $B_{l-1}$ and $D$ \ia\
$\Call(B_{l-1},D)$ and so forth. Finally we interchange $B$ and $D$ \ia\
$\Call(B,D)$. Notice that this series of interchanges has not affected
any of the $\Call(A_j,A_{j+1})$ calls of the list.

In both cases (1) and (2) we subsequently put $E = A_k$ and
interchange $A_{k-1}$ and $E$ \ia\ $\Call(A_{k-1},E)$, $A_{k-2}$ and $E$ \ia\
$\Call(A_{k-2},E), \ldots, A_1$ and $E$ \ia\ $\Call(A_1,E)$, $A$ and $E$ \ia\
$\Call(A,E)$.

Since the initial list $L$ was complete, after each interchange, by Lemma~3,
each new list is complete. Moreover since the process of interchange leaves
the number of calls and the number of people invariant the final list is in
$\Clistset_N$. However by construction the final list contains two calls
between $D$ and $E$ which contradicts Lemma~2.
\smallskip

{\bf Lemma 5.} If $\Call(A,B)$ is a call of $L \in \Clistset_N$, and if
$\Call(A,B)$ is the last call of $A$ then it is also the last call of $B$.

{\bf Proof.} After $\Call(A,B)$ $B$ knows everything, since $\Call(A,B)$
is the last call for $A$. If subsequently $B$ calls $C$ then \ib\ 
$\Call(B,C)$ $B$ and $C$ have common information $c$, which contradicts
Lemma~4.
\smallskip

4. We can now prove that $\Clistset_N$ is empty. Let $L \in \Clistset_N$.
Each person has a last call in $L$. Denote the set of last calls in $L$
by $P$. Let $\Call(A_1,A_2)$ be the final call of $L$ which is not in $P$
(existence obvious). Suppose the last call of $A_1$ is $\Call(A_1,A_3) \in P$,
of $A_2$ is $\Call(A_2,A_4) \in P$. Of course $A_1$, $A_2$, $A_3$ and $A_4$
are all distinct. It is immaterial whether $\Call(A_1,A_3)$ is before of
after $\Call(A_2,A_4)$. By Lemma~4 the information known by $A_1$ and $A_2$
\ia\ $\Call(A_1,A_2)$ is just complementary to the information known by
$A_3$ and $A_4$ at that moment. Hence the information known to $A_3$ and
$A_4$ at that moment is identical.

We may suppose without loss of generality that the penultimate call of
both $A_3$ and $A_4$ is $\Call(A_3,A_4)$. For if the penultimate calls
differ and the last of these is, say, $\Call(A_3,A_5)$ then $A_3$, $A_4$
and $A_5$ have exactly the same knowledge \ia\ $\Call(A_3,A_5)$. We now
interchange $A_4$ and $A_5$ \ia\ $\Call(A_3,A_5)$ and in so doing obtain
a new list $L'$, complete by Lemma~3, $L' \in \Clistset_N$, and having the
required property.

To summarize we can suppose there are calls of $L$ $\Call(A_1,A_3) \in P$,
$\Call(A_2,A_4) \in P$ with the previous call of $A_1$ and $A_2$ being
$\Call(A_1,A_2) \not \in P$ and the previous call of $A_3$ and $A_4$ being
$\Call(A_3,A_4) \not \in P$. A moment's thought reveals there is no loss of
generality in supposing that $\Call(A_3,A_4)$, $\Call(A_1,A_2)$,
$\Call(A_1,A_3)$, $\Call(A_2,A_4)$ are the last four calls of $L$.

Neither $\Call(A_3,A_4)$ nor $\Call(A_1,A_2)$ are the first calls of one
of them in $L$, since $N > 4$ and so there would be no opportunity for
them to learn the remaining information. In view of Lemmas~2 and 4 the
first calls of $A_1$, $A_2$, $A_3$ and $A_4$ are made with new people,
say $B_1$, $B_2$, $B_3$ and $B_4$. It is easy to see that
$B_1$, $B_2$, $B_3$ and $B_4$ are distinct and hence $N \ge 8$ (although
this is not crucial to the argument). Identify $A_1$ and $B_1$,
subsequently $A_2$ and $B_2$, $A_3$ and $B_3$, $A_4$ and $B_4$.
Then by Lemmas~1 and 2 we have a complete list of calls for $N - 4$
ladies with $\f(N) - 4$ calls. Moreover in this new list, by Lemma~1,
$A_1 B_1$ etc. knows at least as much as $A_1$ and $B_1$ together \ia\
the corresponding call in $L$. But this means that \ib\ the last four
calls everyone in the new list knows everything, since at that moment
$B_1$, $B_2$, $B_3$ and $B_4$ know everything in $L$. Hence the last
four calls in the new list are superfluous. Thus we have obtained a
complete list of calls for $N - 4$ persons with $\f(N) - 8 < 2(N-4) - 4$
calls thereby contradicting the minimality of N.
\smallskip

{\bf Remark} due to Wirsing. It is an immediate consequence of the second
form of the problem that a complete list reversed is a complete list and
furthermore the reverse $L^{-1}$ of $L \in \Clistset_N$ also belongs to
$\Clistset_N$. A list in which each pair of ladies who have a common call
have no information \ib\ this call (compare Lemma~4) has a corresponding
product matrix only consisting of entries 1.
\bigbreak

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%Author:  
%Title:   
\vsize=25cm
\font\sc=cmcsc10
\def\f{f}  % minimum number of calls needed
\def\ca{\bar{c}}
\def\cb{\hat{c}}
\def\cc{c_1}

\centerline{\bf A Cure For The Telephone Disease}
\centerline{{\sc A. Hajnal}, {\sc E. C. Milner} and {\sc E. Szemer\'edi}%
\footnote{*}{Research supported by National Research Council Grant
A-5198}}
\centerline{Canad. Math. Bull. 15 (1972), 447--450}

The following problem due to A. Boyd, has enjoyed a certain popularity in
recent months with several mathematicians. A different solution to the one
given here has been given independently by R. T. Bumby and J. Spencer.
(Since this paper was written we have received another solution from R. 
Tijdeman.)

The Problem. There are n ladies, and each of them knows an item of scandal
which is not known to any of the others. They communicate by telephone, 
and whenever two ladies make a call, they pass on to each other, as
much scandal as they know at that time. How many calls are needed before 
all ladies know all the scandal?

If $\f(n)$ is the minimum number of calls needed, then it is easy to verify
that $\f(1) = 0$, $\f(2) = 1$, $\f(3) = 3$ and $\f(4) = 4$.
It is also easy to see that $\f(n+1) \le \f(n) + 2$, for the $(n+1)$-th
lady first calls one of the others and someone calls her back after the
remaining $n$ ladies have communicated all the scandal to each other.
It follows that $\f(n) \le 2n - 4$ $(n \ge 4)$. We will prove that
$$
\f(n) = 2n - 4 \qquad (n \ge 4)  \eqno(1)
$$
We shall represent the $n$ ladies by the set of vertices, $V$, of a
multigraph. A sequence of calls
$$
c(1), c(2), \dots, c(t)  \eqno(2)
$$
between them can be represented by the edges of the multigraph
labelled according to the order in which the calls are made.

{\it The interchange rule}. Suppose (2) is a given sequence of calls, 
and suppose that the 
$a$ calls $c(i)$, $c(i+1)$, \dots, $c(i+a-1)$ are
vertex disjoint from the succeeding 
$b$ calls $c(i+a)$, $c(i+a+1)$, \dots, $c(i+a+b-1)$.
Then we can interchange the order of these two blocks of $a$ and $b$
calls, i.e. if we make the same calls as in (2) but in the order
$$
c(1), \dots, c(i-1), c(i+a), \dots, c(i+a+b-1), c(i), \dots, c(i+a-1),
c(i+a+b), \dots, c(t)
$$
then the total information conveyed is exactly the same as for the
sequence (2). If $c'(1)$, \dots, $c'(t)$ is a rearrangement of the
sequence (2) obtained by a number of interchanges of adjacent blocks
of vertex disjoint calls of the kind just described, we say that $c'$
is an {\it equivalent} calling system and write $c' \sim c$.

Let (2) be a given sequence of calls. A vertex $x$ of the graph will
be called an $F$-point if the corresponding lady knows everything
after the $t$ calls have been made. Obviously, if $c' \sim c$, then
the sequence of calls $c'(1)$, \dots, $c'(t)$ gives the same $F$-points
as $c$. In order that there be any $F$-points at all, the graph $G$,
with vertex set $V$ and edge set (2), must be connected. Consequently,
we have
\smallskip

{\bf Lemma 1.} There are no $F$-points after $n-2$ calls.
\smallskip

In order to prove (1) it is enough to prove
\smallskip

{\bf Lemma 2.} After $n+k-4$ calls there are at most $k$ $F$-points.
\smallskip

{\bf Proof.} We shall actually prove the following stronger assertion
$P(k)$: \hfill
\item{$\bullet$} 
If $c(1)$, \dots, $c(n+k-4)$ is a sequence of $n+k-4$ calls,
then there are at most $k$ $F$-points. 
\item{$\bullet$} 
Further, if there are $k$ $F$-points, 
then there is an equivalent calling sequence $c' \sim c$
in which the last $k$ calls 
$$
 c'(n-3), c'(n-2), \dots, c'(n+k-4)
$$
are all between $F$-points.

The first part of $P(k)$ follows from Lemma 1 if $k=0$, 1, or 2 and 
for these values of $k$ the second part of $P(k)$ is satisfied vacuously.
We now assume that $k>2$ and use induction on $k$.

Suppose there are $k+1$ $F$-points after the $n+k-4$ calls. Since the
last call $c(n+k-4)$ can produce at most two $F$-points, it follows
from the induction hypothesis that there must be $k-1$ $F$-points
$\{ x_1, \dots, x_{k-1} \}$ after the first $n+k-5$ calls and the last
call $c(n+k-4)$ is between two additional $F$-points $\{ x_k, x_{k+1} \}$.
By the second part of $P(k-1)$, we can assume that the last $k-1$ calls
of the sequence $c(1)$, \dots, $c(n+k-5)$ are between the $F$-points
$\{ x_1, \dots, x_{k-1} \}$. By the interchange rule, the last call 
$c(n+k-4)$ could be made before $c(n-3)$, \dots, $c(n+k-5)$. It follows 
that after the $n-3$ calls
$$
 c(1), c(2), \dots, c(n-4), c(n+k-4)
$$
there would by two $F$-points $\{ x_k, x_{k+1} \}$ contrary to Lemma 1. 
This shows that there can be at most $k$ $F$-points.

To complete the proof we must show that the second part of the inductive
statement $P(k)$ holds.

Suppose there are $k$ $F$-points after the $n+k-4$ calls
$$
 c(1), c(2), \dots, c(n+k-4).
$$
Consider the disconnected graph $G_0$ with vertex set $V$ and edge set
$E_0 = \{c(1), \dots, c(n-2)\}$. Suppose $G_0$ has an isolated vertex $x$.
There are at least $k-1$ $F$-points $x_i \neq x$ $(1 \le i < k)$ and each
of these is connected to $x$ by a path from the edge set 
$E_1 = \{c(n-1), \dots, c(n+k-4)\}$. This implies that the points $x$,
$x_i$ $(1 \le i < k)$ are in a single component of the graph $G_1$ on $V$
with edge set $E_1$. This is impossible since $|E_1| + 1 < k$. Thus
$G_0$ has no isolated vertex and each component of this graph has at
least one edge. By the interchange rule, the first $n-3$ calls can be
equivalently re-ordered so that the $(n-3)$-rd call is in a different
component of $G_0$ to $c(n-2)$. Therefore, we may assume that $c(n-3)$
and $c(n-2)$ are disjoint.

Now suppose that the last $k$ calls of the given sequence are not all
between $F$-points. Then there is $p$, $1 \le p \le k$, such that the
last $p-1$ calls $c(n+k-p-2), \dots, c(n+k-4)$ are all between $F$-points
but the preceding call, $c(n+k-p-3)$, is adjacent to at most one $F$-point.
In fact, we can assume that $p < k$. For, if $p = k$ we can, by the last
paragraph, consider instead the equivalent calling sequence obtained by
interchanging $c(n-3)$ and $c(n-2)$.

If $c(n+k-p-3)$ is not adjacent to any $F$-point, then by the 
interchange rule, this call could be made last and then there would be
$k$ $F$-points after only $n+k-5$ calls
$$
 c(1), \dots, c(n+k-p-4), c(n+k-p-2), \dots, c(n+k-4).
$$
This contradicts the induction hypothesis and so we can assume that
$c(n+k-p-3)$ is adjacent to exactly one $F$-point.

Consider the graph $G_2$ on $V$ having the $p$ edges 
$c(n+k-p-3),\dots, c(n+k-4)$ 
and let $C$ be the component of this graph containing the edge
$c(n+k-p-3)$. Let $\ca(1)=c(n+k-p-3)$, $\ca(2), \dots, \ca(r)$
be the edges of $C$ in the order in which these calls are made and let 
$\cb(1), \cb(2), \dots, \cb(p-r)$ be the remaining edges of $G_2$
in order. By the interchange rule, $\cb(1)$ can be made before any of
the calls in $C$ and similarly for $\cb(2), \dots, \cb(p-r)$. Thus
the original calling sequence is equivalent to the sequence of calls
$$
 c(1), c(2), \dots, c(n+k-p-4), \cb(1), \dots, \cb(p-r), 
 \ca(1), \dots, \ca(r).  \eqno(3)
$$
Since $\ca(1)$ is adjacent to only one $F$-point, the component $C$
contains at most $r$ $F$-points ($C$ has $r$ edges and at most $r+1$
points). It follows that after the first $n+k-r-4$ calls in the sequence
(3), there are at least $k-r$ $F$-points. Therefore, by the induction
hypothesis there must be exactly $k-r$ such $F$-points (and the component
$C$ contains exactly $r$ $F$-points) and there is an equivalent 
re-ordering of these $n+k-r-4$ calls so that the last $k-r$ are between
the $k-r$ $F$-points not in C. In this way we obtain an equivalent
calling sequence, say
$$
 c_1(1), \dots, c_1(n+k-r-4), \ca(1), \dots, \ca(r).  \eqno(4)
$$
Since the $k-r$ calls $c_1(n-3), \dots, c_1(n+k-r-4)$ are vertex
disjoint from $\ca(1), \dots, \ca(r)$ (they are between $F$-points
not in $C$) it follows, again by the interchange rule, that an
equivalent sequence is
$$
 c_1(1), \dots, c_1(n-4), \ca(1), \dots, \ca(r),
 c_1(n-3), \dots, c_1(n+k-r-4).  \eqno(5)
$$
The first $n-4+r$ calls in the sequence (5) give rise to the $r$ $F$-points
in $C$. Therefore, by the induction hypothesis, these calls can be 
rearranged so that the last $r$ calls are between $F$-points. After
re-ordering the first $n+r-4$ calls of (5) in this way we obtain an
equivalent calling system $c' \sim c$ in which the last $k$ calls are
all between $F$-points. This completes the proof of Lemma 2.

\bigbreak
\vfill\eject
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\def\bib{\par\noindent\hangindent 20pt}

\centerline{ {\bf References} }

\bib
[1] \enspace
Brenda Baker, Robert Shostak;
Gossips and telephones,
Discrete Mathematics 2 (1972) 191--193.
MR~46~\#~68.

\bib
[2] \enspace
Gerald Berman;
The gossip problem,
Discrete Mathematics 4 (1973) 91 (Corrigendum p397).
MR~46 \#~7037. {\it This proof is incomplete.}

\bib
[3] \enspace
J.-C. Bermond;
Le probl\`eme des ``ouvroirs'',
Colloq. Internat. CNRS, 260, CNRS, Paris, 1978. 31--34.
MR~81c:05056.

\bib
[4] \enspace
Richard T. Bumby;
A problem with telephones,
SIAM Journal on Algebraic and Discrete Methods 2 (1981) 13--18.
MR~82f:05083.

\bib
[5] \enspace
Norbert Cot; 
Extensions of the telephone problem,
Proceedings of the Seventh Southeastern Conference on 
Combinatorics, Graph Theory, and Computing 
(Louisiana State Univ., Baton Rouge, La., 1976), pp. 239--256.
Congressus Numerantium, No.  XVII, Utilitas Math., Winnipeg, Man., 1976.
MR~55~\#~2375.

\bib
[6] \enspace
Richard K. Guy;
Monthly Research Problems, 1969--75,
American Mathematical Monthly 82 (1975) 995--1004.
(this problem discussed on p. 1001).

\bib
[7] \enspace
F. Harary, A. J. Schwenk;
The communication problem on graphs and digraphs,
J. Franklin Inst., 297 (1974) 491--495.

\bib
[8] \enspace
F. Harary, A. J. Schwenk;
Efficiency of dissemination of information in one-way and two-way
communication networks,
Behavioral Science, 19 (1974) 133--135.

\bib
[9] \enspace
A. Hajnal, E. C. Milner, E. Szemer\'edi;
A cure for the telephone disease,
Canad. Math. Bull. 15 (1972), 447--450.
MR~47~\#~3184.

\bib
[10] \enspace
D. J. Kleitman, J. B. Shearer;
Further gossip problems,
Discrete Mathematics 30 (1980) 151--156.
MR~81d:05068.

\bib
[11] \enspace
David W. Krumme; 
Reordered gossip schemes,
Discrete Mathematics 156 (1996), no. 1-3, 113--140.
MR~97i:68154.

\bib
[12] \enspace
Kenneth Lebensold;
Efficient communication by phone calls,
Studies in Appl. Math. 52 (1973) 345--358.
MR~49 \#~4797.

\bib
[13] \enspace
R. Tijdeman;
On a telephone problem,
Nieuw Archief voor Wiskunde (3) 19 (1971), 188--192.
MR~49 \#~7151.

\bye