Question-connected bipartite graph

156 Views Asked by At

Let $M=\{ m_1, \dots , m_r\}$ and $N=\{ n_1, \dots , n_l \}$,where $r,l \in \mathbb{N} \text{ and } 1 \leq r \leq l $. It is also given that $G$ is a coherent bipartite graph,with sets of vertices $N$ and $M$.

Is the diameter equal to $2$,OR between:

-$2r$ and $2l$

-$r$ and $l$

-$2$ and $2r$

-$2$ and $r$

1

There are 1 best solutions below

11
On

$$|M|=r\leq l=|N|$$

Since $G$ is bipartite, the longest possible path is the path that starts and ends in $N$ and contains all of the vertices of $M$. So if the path looks like $(n_1,m_1,...,m_r,n_k)$ where $r\leq k$, you could travel through maximally $2r$ edges because you have to enter and exit every vertex of $M$.