# Is this graph bipartite?

A planar depiction of a loop-free connected graph has 7 regions, each is a polygon. The numbers of edges on the boundaries of the regions are respectively 3,3,3,3,3,4,5. (a) Find the number of vertices of the graph. (b) Is G bipartite?

I figured out that part a) is 7 vertices. So now we have

|V| = 7 |F| = 7 and |E| = 12

so for part b) I began trying to draw sample graphs and my initial intuition is that it isn't but how do I go ahead and properly prove that?

• Are you acquainted with the theorem that a graph is bipartite if and only if it has no odd-length cycles? – saulspatz Dec 6 '18 at 21:13
• Yes, I was just reading into that. But didn't really understand it fully. I will read the link you have provided. – DevAllanPer Dec 6 '18 at 21:15
• Still need help on this – DevAllanPer Dec 6 '18 at 22:16
• @DevAllanPer: Math.SE gets a lot of traffic, so, very unfortunately, not every question gets the attention one might like ... or as quickly as one might like. "Bumping" a question with a "still need help" edit is not the appropriate way to bring more attention to it. – Blue Dec 6 '18 at 22:32
• There is a region bounded by three edges. Can you two-color its vertices? – saulspatz Dec 6 '18 at 22:34