2) Let G be a bipatite graph with 8 vertices and 13 edges. Prove that G is not planar.
I got this one as well.
I still need help with the first one, though..
I have a couple of questions.
1) I'm checking whether two graphs are isomorphic. They have the same number of vertices and edges, they have an equal number of vertices of a certain degree, and I can't construct an isomorphism. I'm lost.
However, one of them has a 3-cyle, while the other one does not. Does this mean anything?
2) Let G be a bipatite graph with 8 vertices and 13 edges. Prove that G is not planar.
3) Let G be a simple graph with v>=2 vertices and e edges, If e<v-1, prove that G is not connected.
Edit: I think I got this one.
Assume that G is connected. Then it contains a spanning tree T. For every tree T: e(T)=v(T)-1, so we have e(G)>=e(T)=v(T)-1, which is a contradiction.
Thank you for your help!