Explore BrainMass
Share

# Automata and Computability

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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.

https://brainmass.com/computer-science/files/automata-computability-113567

#### Solution Preview

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.

\$2.19