Definition of bipartite graph from Murty-Bondy book

165 Views Asked by At

I was reading reading the definition of bipartite graph and one moment is confusing me. Due to this definition we can consider any graph $G=(V,E)$ as a bipartite, if we take $X=\varnothing$ and $Y=V$. However, I am sure that my reasoning is false.

Am I missing something here?

enter image description here

2

There are 2 best solutions below

16
On BEST ANSWER

Yes, you are missing the part that "every edge has one end in $X$ and one end in $Y$." Unless $G$ has no edges, you cannot have $X=\emptyset$ or $Y=\emptyset$.

1
On

As an additional facet to the other answer, a graph is bipartite if there is a way of separating the vertices so that every edge connects one part to the other. Since in modern logic, any universal statement about an empty set is true, if there are no edges then vacuously it is bipartite no matter the partition you use.

So, we get if the edge set is empty, it is bipartite whether or not we allow the partition to be the trivial one. If the edge set is nonempty, the trivial partition will not work to demonstrate if it is bipartite or not. So, the only "advantage" we get of allowing the trivial partition (One set empty, the other the whole space) is we get to consider the fully empty graph: No vertices, no edges to be bipartite (As the only partition of the empty graph is into two empty sets of vertices).

Since we'd like to include the empty set as bipartite (Vacuously so), we need to allow the empty set to be a partition in this case.