# Automata and Computability

An undirected graph is bipartite if its nodes may divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn't contain a cycle that has an odd number of nodes.

See attached file for full problem description.

© BrainMass Inc. brainmass.com October 9, 2019, 7:17 pm ad1c9bdddfhttps://brainmass.com/computer-science/files/automata-computability-113567

#### Solution Preview

Please see attached file.

Problem 39

An undirected graph is bipartite if its nodes may divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn't contain a cycle that has an odd number of nodes.

Let

BIPARTITE = {G | G is bipartite graph}.

Show that BIPARTITE NL.

Solution.

First we show that if a graph is bipartite, it must not contain a cycle with

an odd number of nodes. Suppose it did contain such a cyle. Label the

nodes n1; n2; ::::n2k; n2k+1. Clearly, if n1 is in some set A, then n2 must

be in set B, so n3 must be in set A, etc. By induction, we see ...

#### Solution Summary

The expert examines automata and computability.