draw a planar connected graph with 81 vertices and maximum degree 4 and diameter 6

186 Views Asked by At

I have problem with drawing a planar connected graph with 81 vertices and maximum degree 4 and diameter 6. at first I draw a big plus and tried to put as much vertices as possible on it so that degrees of all vertices is at most 4 and we can walk from every vertex to another one by going over at most 6 edges and try not to crash the edges ,but I could just put 43 vertices in my graph and if I try to add some vertices ,the diameter will be bigger than 6! I will really appreciate any help or idea