0
$\begingroup$

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: enter image description here

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.

$\endgroup$
  • $\begingroup$ Try to apply the definition of a bipartite graph. $\endgroup$ – noedne Apr 13 '18 at 0:15
  • 1
    $\begingroup$ That graph is bipartite. $\endgroup$ – Mike Earnest Apr 13 '18 at 0:16
  • $\begingroup$ @MikeEarnest would a graph with two vertices also be bipartite? I understand the idea of partite sets but Wolfram Alpha seems to indicate that a 2 vertex graph with an edge between the vertices is bipartite mathworld.wolfram.com/BipartiteGraph.html $\endgroup$ – ch1maera Apr 13 '18 at 0:20
  • 1
    $\begingroup$ @ch1maera Yes, the two vertex graph, • – •, is bipartite. Let A be the set consisting of one vertex, and B be the set consisting of the other. Then every edge (i.e, the only edge) of the graph connects some vertex in A to some vertex in B. $\endgroup$ – Mike Earnest Apr 13 '18 at 0:23
1
$\begingroup$

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):

enter image description here

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

enter image description here

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.