3
$\begingroup$

For each $n$, where $n>=3$, are there any graphs in the set of all graphs with $n$ vertices that are simple and planar, and have the most possible number of edges, that also have an Eulerian path or cycle?

for example, one of the graphs in the set I am describing for $n=7$ is as follows:

planar graph with degree sequence 3,4,4,4,5,5,5

yet this graph obviously does not contain an Euler path or cycle, as there are more than two vertices with odd degree.

$n=3$ is an obvious case, as the only such graph is Eulerian.

$\endgroup$
  • $\begingroup$ The complete graph on three vertices? $\endgroup$ – Arthur Aug 30 '18 at 5:56
  • $\begingroup$ @Arthur well duh $\endgroup$ – micsthepick Aug 30 '18 at 5:57
  • $\begingroup$ I will change the question to ask for each number of vertices $\endgroup$ – micsthepick Aug 30 '18 at 5:57
  • $\begingroup$ I edited my answer since I've also found a graph with $n = 7$ that satisfies the given conditions. You can check that as well. $\endgroup$ – ArsenBerk Aug 30 '18 at 7:11
3
$\begingroup$

EDIT:
I have just realised that the simplest solution is to use an $(n-2)$-gonal bipyramid. That is to say, take two pyramids that have a regular $(n-2)$-gon as their base, and stick them together base to base. The vertices around the shared base all have degree $4$, so there are at most two vertices with odd degree (the pyramid tips), and it will have a Eulerian path or circuit. It is a convex polyhedron, so its edge graph is planar. It has $3(n-2)$ edges, so its edge graph is maximal.

Previous solution follows below.


Here I'll describe a construction, based on ArsenBerk's answer, which works for any number of vertices $n>4$. It constructs a planar graph with triangular faces, and with an Eulerian path or circuit.

Start with an $n$-gon. We now triangulate it twice, but the way we do it is slightly different for even and for odd $n$. For even $n$ we use two "zig-zag" triangulations as illustrated here for $n=8$.

enter image description here

The two triangulations start and end at the same pair of opposite vertices, so every vertex has even degree, and the graph has an Eulerian circuit. This easily generalises for all $n>4$, but fails for $n=4$ since in that case the two triangulations degenerate to be identical, making the graph not simple.

For odd $n$ you can use a fan-like triangulation, adding all diagonals from one of the vertices. The two triangulations must fan out from adjacent vertices because otherwise you get a duplicate edge. Here is an illustration for $n=7$.

enter image description here

The two adjacent vertices have degree $2+n-3=n-1$, which is even. The two vertices next to them have degree 3, and all the others have degree 4. The graph has only two odd degree vertices, so has an Eulerian path.

These graphs are planar. You can draw them so that one triangulation is inside the $n$-gon, and the other inverted on the outside. You can kind of think of it as a degenerate convex polyhedron, consisting of an $n$-gon around its equator with one triangulation on top and another on the bottom. As with a normal convex polyhedron you can expand a face in the top half to get a planar graph of the polyhedron edges.

Every face is triangular, so we cannot add any further edges to the graph. In fact, no graph is possible with more edges, and this can easily be proved using Euler's formula. In a planar graph every face has at least $3$ edges, and every edges borders $2$ faces, so $3F\le2E$. Putting this into Euler's formula $V-E+F=2$ you get $E\le3V-6$. In these graphs the number of edges is $n+2(n-3) = 3n-6$, so this maximum is attained.

$\endgroup$
2
$\begingroup$

For example for $n = 5$, the following simple graph has the most possible number of edges, as well as planar and also has Eulerian path since it has three vertices with degree $4$ and two vertices with degree $3$:

enter image description here

Also note that it lacks only one edge to be the complete graph $K_5$ and since $K_5$ is not planar, above graph has the most possible number of edges with given conditions.

Besides, now that I checked for $n = 7$, I also found a simple and planar graph with $15$ edges (same as yours) that has Eulerian path. It's construction is as same as the graph with $n = 5$ so maybe for $n = 9$, we can also find such graph. The following graph has two vertices with degree $6$, three vertices with degree $4$ and two vertices with degree $3$:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Basically you can take an $n$-gon and triangulate it in two ways. Draw one triangulation normally inside the $n$-gon, and the other inverted on the outside. You can kind of think of it as a degenerate convex polyhedron, consisting of an $n$-gon around its equator with one triangulation on top and another on the bottom. As with a normal convex polyhedron you can expand a face in the top half to get a planar graph of the polyhedron edges. $\endgroup$ – Jaap Scherphuis Aug 30 '18 at 9:27
  • $\begingroup$ But I'm not sure if this works for even $n$. For example $n = 4$ gives $K_4$ which doesn't have Eulerian path or cycle and when $n = 6$, the same construction yields a graph with three vertices of odd degree. $\endgroup$ – ArsenBerk Aug 30 '18 at 9:35
  • $\begingroup$ You're right, what I wrote is not enough. Not only does the graph have to be simple, so the two triangulations must not have any connected pair of nodes in common, they must also be such that at least $n-2$ nodes have an even degree. It can always be done for odd $n$, but I'm still working out for which even values it is possible, if any. $\endgroup$ – Jaap Scherphuis Aug 30 '18 at 9:42
  • $\begingroup$ Yes, that's right. But even though what you wrote was not enough, you explained the construction algorithm well enough I think, as well as proved it for all odd $n$. Since OP asked existence, I never tried to prove it more generally. $\endgroup$ – ArsenBerk Aug 30 '18 at 9:44
  • 1
    $\begingroup$ I think $n=6$ is possible. If the hexagon is $ABCDEF$, use one triangulation connecting $AE$, $EB$, and $BD$, and the other triangulation $DF$, $FC$, $CA$. So it is $K_6$ with $3$ edges removed, one from each node, so all have degree 4.. $\endgroup$ – Jaap Scherphuis Aug 30 '18 at 9:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.