Sorry if the question is too basic. I know that a complete bipartite graph k_{n,m} has a diameter equals one when m=n=1 and 2 otherwise. My question is about a bipartite graph K_{n,n} with two partite sets of vertices U and V of size n where each vertix from U is adjacent to only one vertix from V. What is the diameter of this graph?
Thank you
[Math] Diameter of bipartite graph
graph theory
Related Solutions
You can bound $\lvert N(S)\rvert$ from below by considering the worst case that all neighbours have the maximal degree, $n-d+1$. Then each vertex in $S$ of degree $n-d+1$ has as many outgoing edges as a worst-case neighbour has incoming edges, so the "cost balance" of such a vertex is neutral. Each vertex in $S$ of degree $n-d$ "saves" one edge, but there can be at most $n-d$ of these in $S$, so only $n-d$ edges can be "saved", whereas $n-d+1$ edges would have to be "saved" to "save" one worst-case neighbour. So no neighbour can be "saved" even in the worst case, and thus there must be as many neighbours as vertices in $S$.
I can write that out in formulas if you want, but you said you wanted a hint.
[Edit in response to request for formulas:]
Since all edges incident at a vertex in $S$ are also incident at a vertex of $N(S)$, we have
$$\sum_{w\in N(S)}\deg(w)\ge\sum_{v\in S}\deg(v)\;.$$
If $S$ contains $n_-$ vertices of degree $n-d$ and $n_+$ vertices of degree $n-d+1$, then
$$\begin{eqnarray} \sum_{v\in S}\deg(v)&=&n_-(n-d)+n_+(n-d+1)\\\ &=&(n_-+n_+)(n-d+1)-n_-\\\ &=&\lvert S \rvert (n-d+1)-n_-\\\ &\ge&\lvert S \rvert (n-d+1)-(n-d)\;, \end{eqnarray}$$
since there are only $n-d$ vertices of degree $n-d$. On the other hand, since no vertex has degree more than $n-d+1$, we also have
$$\sum_{w\in N(S)}\deg(w)\le \lvert N(S) \rvert (n-d+1)\;.$$
Putting this all together gives
$$\lvert N(S) \rvert (n-d+1) \ge \lvert S \rvert (n-d+1)-(n-d)\;,$$ $$\lvert N(S) \rvert \ge \lvert S \rvert -\frac{n-d}{n-d+1}\;.$$
But $\lvert N(S) \rvert$ and $\lvert S \rvert$ are integers and the last term is less than $1$, so we can drop the last term to conclude that $\lvert N(S) \rvert\ge\lvert S \rvert$. Linking this back to the original answer, each vertex in $S$ of degree $n-d$ can change the balance in the penultimate inequality by at most $1$, and there are at most $n-d$ such vertices, so the balance can only be changed by $n-d$, but it would have to change by $n-d+1$ to make a difference in the last inequality, where the division by $n-d+1$ corresponds to the fact that we need to "save" $n-d+1$ edges in order to "save" one worst-case neighbour.
Let's see if I understand the problem correctly. Given a tree $T$ on $2n$ vertices, you want to create a bipartite graph $G$, on the same vertex set, with bipartition $(A,B)$ such that $|A|=|B|=n$. You want $G$ to be connected, but you want each edge in $G$ to join two vertices at distance at most $k$ in the tree $T$, for the least possible $k$.
Here is the optimal way to do this, which achieves $k=2$. Start with the ordinary bipartition of $T$. Suppose that in this bipartition $|A|>|B|$.
In this case, set aside all the leaves (degree $1$ vertices) of $T$ that are in $A$; let $A'$ be the set of all non-leaves. We show that there's a matching between $A'$ and $B$ that saturates $A'$: a set of edges of $T$ that include every vertex of $A'$ exactly once, and every vertex of $B$ at most once.
To find the matching, let $u \in A'$ be an arbitrary vertex. Each other vertex $v \in A'$ has at least two neighbors, only one of which lies on the path from $u$ to $v$; pick one that does not lie on that path, and match it to $v$. (We can match $u$ with any neighbor we like.) Two vertices $v_1, v_2 \in A'$ cannot be matched to the same vertex $w \in B$; if so, then there are two paths from $u$ to $w$ (one through $v_1$ and one through $v_2$) which contradicts the definition of a tree. So no vertex of $B$ is used multiple times, and we've found a matching from $A'$ to $B$.
(Exercise: this step could also have been done using Hall's theorem!)
In particular, this means that $|A'| \le |B|$. Since $|A| > |B|$, we know that the difference $|B|-|A|$ is at most the number of leaves in $A$.
Now move leaves from $A$ to $B$ one at a time until $|A|=|B|$. When we move a leaf $u$ from $A$ to $B$, we need to connect it back to the tree; to do this, let $v$ be $u$'s only neighbor ($v \in B$) and let $w$ be any non-leaf neighbor of $v$ ($w \in A$). Add the length-$2$ edge $uw$; now the graph is connected again.
This works for all trees except a star: a tree in which all vertices except one are leaves. In this case, the last step fails because the vertex $v$ has no non-leaf neighbors. But in the star, all distances are at most $2$, so any way we decide to balance it will work.
Best Answer
If each vertex in $U$ is connected to only one vertex in $V$ that your graph consists of $n$ disconnected components. So the diameter is infinite unless $n=1$.