I have the following Bipartite graph, how can I prove that it is connected?
I have been searching the Internet for hours but couldn't find a solution, I need a mathematical method to prove it is connected (not looking for solutions such as run DFS or BFS).
I am looking for a (sufficient) condition on a bipartite graph in terms of the vertex degrees, number of edges etc. that implies the graph is connected
$\endgroup$ 62 Answers
$\begingroup$These two graphs have the same degree sequence:
The one on the left is your (connected) graph, whereas the one on the right is disconnected. So, you're not going to find a mathematical sufficient condition for connectedness based on degree sequences alone.
Also, keep in mind that conditions like "if each vertex has a degree $\geq ( n − 1 ) / 2$ then the graph is connected" are also algorithmic. To verify connectedness, the reader still needs to check each vertex has degree $\geq ( n − 1 ) / 2$.
$\endgroup$ $\begingroup$Since you've tagged this under "matrices", let's use the adjacency matrix $A$.
$A_{ij}^n$ (i.e. entry $ij$ in $A^n$) represents the number of walks of length $n$ between vertices $i$ and $j$. In a connected graph, the maximum distance require to get from any node to any other is $V-1$ where $V$ is the number of vertices. So to test whether a graph is connected, you can compute $\displaystyle\sum_{i=1}^{V-1}A^{i}$: if there are no $0$ entries, the graph is connected. If there are $0$ entries, it's not.
Edit: The requirement seems to be not for a method of proof as originally requested but for a sufficient condition on a bipartite graph to ensure connectedness. This math.SE question, (result #4 of Googling "bipartite graph connected") shows that if each vertex has degree $\frac{n}{4}+1$ then the bipartite graph is connected.
$\endgroup$ 7
