Can a bipartite graph have only 3 vertices?

Question

I'm new to Graph Theory and I'm confused as to whether a bipartite graph needs to be closed (i.e. the vertices are all connected in some way via a walk) or if it can exist like this:

Essentially, I need to use induction on the number of edges in a graph to prove that the absence of odd cycles is all that's needed to declare a graph bipartite and I'm unsure what length to use for the base hypothesis.

Answer 1

The definition of bipartite graph at Wikipedia is:

... a bipartite graph ... is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$.

A bipartite graph doesn't need to be connected. It's fine to have $U$ and $V$ of any size (possibly even empty). We can also have any number of edges (possibly even zero).

Here's an example of a bipartite graph (with $U$ and $V$ indicated by vertex colors):

The graph drawn in the question is complete bipartite graph $K_{1,2}$, and we can highlight sets $U$ and $V$ as shown below:

Answer 2

Yes. Remember that a bipartite graph joins two sets by edges. Think of two islands joined by bridges.

The picture you've provided is certainly bipartite because the lone node is connected to the other two - those remaining vertices cannot be joined by an edge because that violates the definition.

In short, a graph is bipartite if its vertices can be placed in two sets $X$ and $Y$ and the only edges are those between $X$ and $Y$.