Bipartite Graph and Non-Connected Node?

Bipartite Graph and Non-Connected Node?
$\begingroup$

Is this one bipartite graph or not?

It is a simple question for you but i can't find the answer.

$\endgroup$
4

1 Answer

$\begingroup$

If the top-left vertex was adjacent to all three of the right-side vertices, you would have $K_{3, 3}$, a bipartite graph. The nodes on the left form one partition, and the nodes on the right form another partition. Note that no nodes in a single partition are adjacent. So removing the three edges from the top-left vertex of $K_{3, 3}$ leaves you with your current graph.

So the graph you have is still bipartite, as you have:

-Two sets of vertices

-No pair of vertices in a given partition (set) are adjacent

Edit: Regarding your question on the maximum number of edges a bipartite graph on $n$ vertices can have without being connected. So we have one vertex disconnected. If $n$ is odd, then we have $K_{(n-1)/2, (n-1)/2}$. Otherwise, we have $K_{(n-1)/2, (n-1)/2 + 1}$. Then just count up the edges.

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Chloe Bennett
Author

Chloe Bennett

Chloe Bennett explores the intersection of pop culture, streaming entertainment, digital trends, and contemporary lifestyle. Her weekly commentary reaches thousands of culture enthusiasts.