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?

  • $\begingroup$ Are you acquainted with the theorem that a graph is bipartite if and only if it has no odd-length cycles? $\endgroup$ – saulspatz Dec 6 '18 at 21:13
  • $\begingroup$ Yes, I was just reading into that. But didn't really understand it fully. I will read the link you have provided. $\endgroup$ – DevAllanPer Dec 6 '18 at 21:15
  • $\begingroup$ Still need help on this $\endgroup$ – DevAllanPer Dec 6 '18 at 22:16
  • $\begingroup$ @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. $\endgroup$ – Blue Dec 6 '18 at 22:32
  • $\begingroup$ There is a region bounded by three edges. Can you two-color its vertices? $\endgroup$ – saulspatz Dec 6 '18 at 22:34

Also, the graph on part a) could look like this:enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.