graph theorymatrices
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
If there's a cut-vertex $v$, some neighbor of $v$ induces in $G \setminus \{v\}$ a connected bipartite graph with bipartition $A \cup B$. It looks something like:
We observe:
This is a contradiction.
There are infinitely-many counterexamples to the claim as stated. Consider the graph on $n+1$ vertices where $v$ is connected to each of the other $n$ vertices but no other edges are included (this is sometimes called the star graph $S_{n+1}$). The graph is bipartite: put $v$ in one set and the remaining $n$ vertices in another.
As noted in the comments, these are the only counterexamples to the claim. A graph is bipartite if and only if all of its cycles have even length. If $S_{n+1}$ is given even one more edge, it will contain a cycle of length three, and so will not be bipartite.
Best Answer
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$.