2 deleted 8 characters in body

# Husk, 17 bytes

§V¤=ṁΣṠMSȯDfm¬ṀfΠ


Prints a positive integer if the graph is bipartite, 0 if not. Try it online!

## Explanation

This is a brute force approach: iterate through all subsets S of vertices, and see whether all edges in the graph are between S and its complement.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
Π  Cartesian product; result is X.
Elements of X are binary lists representing subsets of vertices.
If M contains an all-0 row, the corresponding vertex is never chosen,
but it is irrelevant anyway, since it has no neighbors.
All-1 rows do not occur, as the graph is simple.
ṠM           For each list S in X:
Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
S  fm¬     then filter the result by the element-wise negation of S,
ȯD        and concatenate the resulting matrix to itself.
Now we have, for each subset S, a matrix containing the edges
from S to its complement, counted twice.
§V                 1-based index of the first matrix
¤=               that equals M
ṁΣ             by the sum of all rows, i.e. total number of 1s.
Implicitly print.


# Husk, 17 bytes

§V¤=ṁΣṠMSȯDfm¬ṀfΠ


Prints a positive integer if the graph is bipartite, 0 if not. Try it online!

## Explanation

This is a brute force approach: iterate through all subsets S of vertices, and see whether all edges in the graph are between S and its complement.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
Π  Cartesian product; result is X.
Elements of X are binary lists representing subsets of vertices.
If M contains an all-0 row, the corresponding vertex is never chosen,
but it is irrelevant anyway, since it has no neighbors.
All-1 rows do not occur, as the graph is simple.
ṠM           For each list S in X:
Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
S  fm¬     then filter the result by the element-wise negation of S,
ȯD        and concatenate the resulting matrix to itself.
Now we have, for each subset S, a matrix containing the edges
from S to its complement, counted twice.
§V                 1-based index of the first matrix
¤=               that equals M
ṁΣ             by the sum of all rows, i.e. total number of 1s.
Implicitly print.


# Husk, 17 bytes

§V¤=ṁΣṠMSȯDfm¬ṀfΠ


Prints a positive integer if the graph is bipartite, 0 if not. Try it online!

## Explanation

This is a brute force approach: iterate through all subsets S of vertices, and see whether all edges in the graph are between S and its complement.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
Π  Cartesian product; result is X.
Elements of X are binary lists representing subsets of vertices.
If M contains an all-0 row, the corresponding vertex is never chosen,
but it is irrelevant anyway, since it has no neighbors.
All-1 rows do not occur, as the graph is simple.
ṠM           For each list S in X:
Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
S  fm¬     then filter the result by the element-wise negation of S,
ȯD        and concatenate the resulting matrix to itself.
Now we have, for each subset S, a matrix containing the edges
from S to its complement, twice.
§V                 1-based index of the first matrix
¤=               that equals M
ṁΣ             by the sum of all rows, i.e. total number of 1s.
Implicitly print.

1

# Husk, 17 bytes

§V¤=ṁΣṠMSȯDfm¬ṀfΠ


Prints a positive integer if the graph is bipartite, 0 if not. Try it online!

## Explanation

This is a brute force approach: iterate through all subsets S of vertices, and see whether all edges in the graph are between S and its complement.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
Π  Cartesian product; result is X.
Elements of X are binary lists representing subsets of vertices.
If M contains an all-0 row, the corresponding vertex is never chosen,
but it is irrelevant anyway, since it has no neighbors.
All-1 rows do not occur, as the graph is simple.
ṠM           For each list S in X:
Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
S  fm¬     then filter the result by the element-wise negation of S,
ȯD        and concatenate the resulting matrix to itself.
Now we have, for each subset S, a matrix containing the edges
from S to its complement, counted twice.
§V                 1-based index of the first matrix
¤=               that equals M
ṁΣ             by the sum of all rows, i.e. total number of 1s.
Implicitly print.