Mathmania Graph Research

Our feature problem asks you to draw a graph.

The graph has to have three special properties.

• It has to be planar.
• It has to have a certain degree.
• It has to have a certain diameter.

If you want to know more about what these things mean, see the graph tutorial. Here is a short summary:

A planar graph is a graph that can be drawn without any edges crossing each other.

The degree of a vertex of a graph is the number of edges which have it as one of its end points. In other words, the degree of a vertex is the number of neighbors it has, not including itself.

The degree of a graph is the largest degree of all its vertices.

The distance between two vertices in a graph is the least number of edges you must encounter in any path from one of the vertices to the other.

The diameter of a graph is the largest of all the distances between two of its vertices. That is, the diameter of a graph is the maximum of all the distances between vertices.

Again, see the tutorial if you need help with these definitions.

Open Problem: The following graph is the largest known planar graph which has diameter=4 and degree=4. Can you find a graph which has MORE VERTICES which is still planar and has diameter=4 and degree=4?

• Note that this graph is planar. It has no crossed edges.
• Has diameter=4. You can get from any vertex to any other vertex without having to use more than 4 edges.
• Has degree=4. Each vertex has no more than 4 edges coming out of it.

Thanks to those who have submitted entries for other versions of this problem. Those entries are being examined, and we will post successful entries soon.

Problem submitted by: Dr.Michael Fellows.
Prize: Mathmania T-shirt.

There are two ways to solve this problem: either find a larger graph with these properties, or prove that it is impossible to draw such a graph.

Please use the resources in the Graph Menu to help you work on this problem.

Graph Menu