Let $G$ be a connected simple graph. When we add an edge to $G$ (between two unconnected vertices), then using at most $17$ edges we can reach any vertex from any other vertex. Find the maximum number of edges to be used to reach any vertex from any other vertex in the original graph, i.e. in the graph before we add an edge.
Problem
Source: Turkey JBMO Team Selection Test Problem 8
Tags: floor function, ceiling function, combinatorics proposed, combinatorics
31.05.2012 12:07
I think that the answer is 18... is't correct?
31.05.2012 17:26
Depends. If "add an edge" means "add any edge", then it's 18. Example is easy (18-edge path), proof that it's impossible to have 19 is easy (if there is a 19-edge path and the new edge connects only the first and the third vertices, the resulting graph has diameter 18). If "add an edge" means "add some edge", then I found 34 but hasn't managed to proceed further. Example is a 34-edge path; connect the two endpoints and we have a 35-edge cycle, making its diameter 17. The above is correct unless I totally misunderstand the problem.
01.06.2012 02:26
The meaning must be the second one described ("add some edge"), since it is interesting, while the first meaning ("add any edge") is kind of trivial. The $34$ diameter example is correct, and the proof for no larger diameter follows. Say the edge $e= ab$ is added. Let the path $P = a\ldots b$ be of minimal length $\ell$ in $G$. It follows $\ell \leq 34$. Let $c\in P$ be such that the length of the path $P(a,c) = a\ldots c \subset P$ is $\lfloor \ell/2 \rfloor$, and so the length of the path $P(b,c) = b\ldots c \subset P$ is $\lceil \ell/2 \rceil$. Let now $x,y$ be any two vertices. If a path $x\ldots c$ of minimal length does contain $e$, then it cannot be $x\ldots aP(b,c)$, since then the path $x\ldots P(ac)$ would be shorter, so it must be $x\ldots bP(a,c)$, but then the path $x\ldots P(bc) \subset G$ is not longer, so $\textrm{d}_{G}(x,c) \leq 17$, in all cases. Similarly $\textrm{d}_{G}(y,c) \leq 17$, hence $\textrm{d}_{G}(x,y) \leq \textrm{d}_{G}(x,c) + \textrm{d}_{G}(y,c) \leq 34$. Therefore $\textrm{diam}(G) \leq 34$; in fact we proved that $\textrm{diam}(G) \leq 2\textrm{diam}(G+e)$.