0
$\begingroup$

Definition: A graph G is bipartite if its vertices can be partitioned into two sets V1 and V2 and every edge joins a vertex in V1 with a vertex in V2. Bipartite graphs can be characterized by all circuits in such graphs having even length (if there are no circuits, the graph is also bipartite), where the length of a circuit or path is the number of edges in it What is the smallest bipartite graph?:

enter image description here

$\endgroup$
4
$\begingroup$

Depends on your definition, but if you define bipartite as two-colorable or having no odd cycles, then the empty graph or the trivial graph are the minimal bipartite graphs.

$\endgroup$
  • $\begingroup$ A graph G is bipartite if its vertices can be partitioned into two sets V1 and V2 and every edge joins a vertex in V1 with a vertex in V2. Bipartite graphs can be characterized by all circuits in such graphs having even length (if there are no circuits, the graph is also bipartite), where the length of a circuit or path is the number of edges in it $\endgroup$ – hit Feb 6 '16 at 0:13
  • $\begingroup$ with this definition it the answer still the same? $\endgroup$ – hit Feb 6 '16 at 0:14
  • 2
    $\begingroup$ Well, if they're allowed to be empty, just take $V_1=V_2=\emptyset$ and the empty graph is bipartite. $\endgroup$ – YoTengoUnLCD Feb 6 '16 at 0:20
1
$\begingroup$

If by "smallest" you mean "number of vertices", then that is one possible answer.

But you could also remove the edge to leave two vertices and no edges, and perhaps you will consider this to be "smaller" than your example.

$\endgroup$
  • $\begingroup$ with the definition I edited into the first post, is the answer still the same? $\endgroup$ – hit Feb 6 '16 at 0:15
  • $\begingroup$ According to the definition you have given, YoTengounLCD's answer is correct. The definition I have mostly seen is that the "parts" of a bipartite graph must be non-empty sets of vertices. $\endgroup$ – David Feb 7 '16 at 4:13

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.