0
$\begingroup$

The question is this:

In each case, give the values of $r$ (number of regions), $e$ (number of edges), or $v$ (number of vertices), whichever is not given, assuming that the graph is planar. Then either draw a connected, planar graph with the property, if possible, or explain why no such planar graph can exist.

  • 8 vertices and 13 edges

Finding $r$ is easy: $$r = e - v +2 = 13 - 8 + 2 = 7$$ so $r = 7$. This is clear to me.

What's not so clear to me is drawing the graph part.

Can I just draw a circle of 8 vertices connected to each other (circuit-wise) and then make random edges connecting two vertices of the circle willy-nilly (as long as they don't cross with other edges) until I reach 13 edges and have 7 regions?

I've seen some people draw a square instead of a circle and I'm a bit confused on that. Is that right? Is there a specific form this graph must take, or is it isomorphic and the form of the graph doesn't really matter as long as you have 8 vertices, 7 regions, and 13 edges that don't overlap with each other?

Thank You

$\endgroup$
1
  • $\begingroup$ You have only determined that if there is a connected planar graph with $8$ vertices and $13$ edges, then it has $7$ faces. You haven't shown that such a graph exists. If one does, you must draw it so that none of the edges cross. Even if such a graph exists, there is no guarantee that it is Hamiltonian, so you may not succeed by putting all the vertices on a circle (though that's a good way to start.) $\endgroup$
    – saulspatz
    Sep 3, 2020 at 4:37

2 Answers 2

2
$\begingroup$

Can I just draw a circle of 8 vertices connected to each other (circuit-wise) and then make random edges

Yes. You will always end up with 7 regions, as guaranteed by r = e - v + 2.

I've seen some people draw a square instead of a circle and I'm a bit confused on that.

They are not wrong; the shape of the graph is irrelevant. However do note that if you draw the vertices on a square, you many obfuscate the fact that you can draw a edge connecting the corners.

Is there a specific form this graph must take, or is it isomorphic and the form of the graph doesn't really matter

According to the wordings of the question, the form doesn't matter, but the graphs you draw may not be isomorphic. The vertices may not even have the same degrees. (e.g. Draw randomly vs all new edges linked to one vertex)

$\endgroup$
1
$\begingroup$

Provided that the values of $e$ and $v$ you get satisfy $e \le 3v-6$ (for the graph to be planar) and $e \ge v-1$ (for the graph to be connected) then a solution will exist. There are many ways to draw it.

Can I just draw a circle of 8 vertices connected to each other (circuit-wise) and then make random edges connecting two vertices of the circle willy-nilly (as long as they don't cross with other edges) until I reach 13 edges and have 7 regions?

That's one way. I'd add that you should also be careful not to draw more than one edge connecting the same pair of vertices.

In fact, if you start with any tree on $8$ vertices (which will have $7$ edges), then make $6$ more random edges connecting two vertices willy-nilly (as long as they don't cross other edges), you will find an example.

There are multiple possible solutions. For example, here is one that you won't be able to get starting from a cycle with $8$ vertices, because one of the vertices has degree $1$:

enter image description here

(The drawing here isn't quite planar, but the graph is, and you can make the drawing planar by shortening the edge from the degree $7$ to the degree $1$ vertex. I took the image from here, after searching House of Graphs for planar graphs with $8$ vertices and $13$ edges.)

Is there a specific form this graph must take, or is it isomorphic and the form of the graph doesn't really matter as long as you have 8 vertices, 7 regions, and 13 edges that don't overlap with each other?

Isomorphic has a technical meaning: as I mentioned above, there are multiple different, non-isomorphic graphs you could get. But for the purposes of this problem, it doesn't matter what the graph you get looks like.

Also, you don't need to take any special care to make sure you have exactly $7$ regions; assuming you draw a planar graph, that will happen automatically.

$\endgroup$

Your Answer

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