Actual responses to actual questions from students of Math 344, Introduction to Combinatorics (Spring 2004).
I get that only graphs (a) and (c) (out of a,b,c,d) are planar. Also, could you please tell me what kind of method one might use to find a K3,3 configuration in a graph?
Your answer is correct. To find a K3,3 configuration, just look at the subgraph in which the non-planarity occurs. (That is, look at the problem piece.) You can delete vertices of degree 2 — just turn two edges like a—b—c into one edge like this: a—c. Either you end up with a K3,3, or you've deleted too much and the resulting graph is planar, or you've deleted too little and the graph is still too complicated. I hope this helps.
For part (d) I got the answer that it is not a planar graph, but it does not have K3,3 configuration, is this right?
Yes.
Please tell me why it is not a K(3,3) configuration.
Well, I'm not sure I understand you. You've just told me that it doesn't have a K3,3 configuration; now you ask why it doesn't have one? It can be non-planar without a K3,3 configuration if it has a K5 configuration. (Hint: look at vertices a,b,c,d,f.)
For part(a), I get that Kn is planar for n = 1, 2, 3, or 4, since for n ≥ 5, the graph contains K5 as a subgraph and hence is non-planar. Is this right?
Yep.
I got the answer n is 3 or 4, not like you said it is 1,2,3,or 4.
So you're saying that K1 and K2 are non-planar? That's not true. (Just draw them!)
Another question regarding this problem is does this mean that if e ≤ 3v-6, then the graph is planar.
Nope. As you say...
From the book, it is not necessary the case, we got K3,3 satisfying this equality, however, it is not planar, so I am just wondering what about the case Kn. why should we conclude that it is planar, if the equation satisfying e≤3v-6
Well, each Kn has a K5 subgraph if n>5. Since K5 is non-planar, this means Kn is non-planar for n>5 as well.
For part (b), I get that the complete bipartite graph Kr,s is planar for:
Yep. As the answer in the book says, this means Kr,s is planar if r≤2 or s≤2
Could you please provide a hint about how to go about solving this problem?
Sure. Suppose you have two disjoint planar graphs, G1 and G2, both of which are connected. Suppose G1 has v1 vertices and e1 edges, bounding r1 regions. Similarly, let v2, e2, and r2 be the same thing for G2. Then (provided e1>1 and e2>1),
r1 = e1 - v1 + 2
r2 = e2 - v2 + 2
Now suppose G is the (disjoint) union of G1 and G2. That is, G is the graph you get by considering G1 and G2 as one graph (but they still don't touch each other). Now notice that the number of vertices of G is v = v1 + v2, the number of edges is e = e1 + e2. What about the number of regions? It's r=r1+r2 -1. Where does the ``-1'' come from? Draw a simple example, and count the regions!
In part (a), I understand how to obtain the value for e, but how do I obtain the value for r?
By ``all regions have the same number of bounding edges d2'' the book means that the ``edge degree'' is d2 for every edge. And just as each edge is bounded by two vertices (so 2e = total of the vertex degrees), so does each edge bounds two regions (so 2e = total of the region degree). Thus 2e = d2 r. Now put r in terms of v by eliminating e, and solve.