This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.


Finds out if a graph is bipartite.

MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.


Graph::bipartite(G, <Bool | Lists>)


Graph::bipartite(G) finds out whether G is bipartite or not.

Graph::bipartite(G, Sets): If G is bipartite, then a list containing two lists will be returned. Each of the lists contains the vertices belonging to the set. If G is not bipartite, then FAIL will be returned instead of any list.

Graph::bipartite(G, Bool) offers the same result as Graph::bipartite(G). If G is bipartite, then TRUE will be returned, otherwise FALSE.


Example 1

A small graph containing 3 vertices with 2 edges connecting them is created:

G := Graph([a, b, c], [[a, b], [b, c]]):
Graph::bipartite(G, Lists); 
Graph::bipartite(G, Bool)

Two lists with vertices are shown. Another word for bipartite is two-colorable. This means that the graph above can be colored with only two colors so that no two vertices have the same color if connected with an edge. The bottom output could also be accomplished without using the parameter Bool:


The following example shows what happens when a graph is not bipartite (an edge is added to connect the vertices a and c):

G2 := Graph::addEdges(G, [[a, c]]):
Graph::bipartite(G2, Lists); 
Graph::bipartite(G2, Bool)






If Lists is stated the return value will be a list of two lists containing the (sorted) vertices belonging to each set, or FAIL.


If Bool is stated the return value will be either TRUE or FALSE. This is the default.

Return Values

Depending on the options either a boolean value or list-sets will be returned.

Was this topic helpful?