CODEWITHSUNDEEP
graph-theory
StevieG
StevieG

Reputation: 309

How to define a connected bipartite graph?

I know what a connected graph is - "A graph is connected when there is a path between every pair of vertices". But I am skeptical about how to define a connected bipartite graph. Is the following correct? "When every vertex in the first subset has a edge with every vertex in the second subset"

Please comment. Need help!

Upvotes: 1

Views: 7358

Answers (1)

Tony Babarino
Tony Babarino

Reputation: 3405

Connected bipartite graph is a graph fulfilling both, following conditions:

  1. Vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge in graph connects a vertex in U to one in V.
  2. There is a path between every pair of vertices, regardless of the set that they are in.

Is the following correct? "When every vertex in the first subset has a edge with every vertex in the second subset"

No it't not:

o----o
    / 
   /
  /
o----o

This is a connected bipartite graph and it's not fulfilling Your definition.

Upvotes: 2

Related Questions