Solution for Section 11.1 Question 4

4. The first graph is bipartite. To see this let V1 = {a,b,d} and V2 = {c,e,f,g} and note that every edge has one endpoint in V1 and one endpoint in V2.

The second graph is not bipartite. If this graph were bipartite then without loss of generality we may assume that a Î V1 and b Î V2. However, then  f cannot belong to either V1 or V2. Hence the graph is not bipartite.

Back to Section 11.1