Search for small alternating planar graphs

Hello everybody,

a planar graph is called alterning when it has

\* no pair of neighboring vertices with the same degree

and

\* no pair of neighboring faces with the same number of sides.

The smallest alternating planar graph I know

has 25 vertices and 25 faces (the outer face is also

in the count). It was constructed by two math students

from Jena university: Katrin Nimczick andLisa Schreiber.

A picture of it can be seen under

[http://www.althofer.de/alternating-planar-graphs.html]

For me it would be a big surprise when there were

no other alternating planar graphs with less then

25 vertices and 25 faces.

Ingo Althofer

Sorry for the misspell:

It should be "alternating" and not alterning.

Ingo

How about the empty graph? :-) [*duck*]

And how about you ask in a place like sci.math.research? That might be a better place for a question like this.

Final comment: are you disallowing vertices of degree 2? If not then here's an example with fewer faces (but more vertices): take a cube, chop off all the edges (so we have six octagon faces and 8 triangles) and now put a vertex in the middle of each side of each triangle. Now we have six 12-gons and eight hexagons; now flatten it out.

*typo*: chop off all the CORNERS! [not edges]

*groan* need a vertex in the middle of each edge, not just the triangle edges. So resulting thing is six 16-gons and eight hexagons. I think I'm OK now though.

ooh---better example (and one that works): start with a cube, and cut off the corners so much that you end up with one of those shapes with 6 square faces and 8 triangle faces. Now put a new vertex in the middle of each edge. How about that? I think this has 6 octagons, 8 hexagons and 36 vertices?

Nice problem. The web page states that each vertex must have degree at least 3 and each face must have at least 3 sides.

Aah. I didn't look at the web page, just the description above, where these extra conditions have carefully been removed :-)

I am no graph theorist, but it wouldn't surprise me if there were standard databases of graphs nowadays online and one could just write a little computer script to check through them to see if one could find smaller examples.

There is the program "plantri" available online that generates planar graphs. A good C-programmer could modify it to search for alternating planar graphs.

Thanks to wccanard and the Tasmanian devil for all

the quick feedback. And e few comments:

wcc proposed:

> how about you ask in a place like sci.math.research?

> That might be a better place for a question like this.

In principle you are right, and I may ask there later,

too. However, in mind I have the use of "nice" alternating

planar graphs for a new board game mechanism. Knowing

this, LG players may be especially motivated to look

for small apg's.

wcc:

> are you disallowing vertices of degree 2?

Right. When you allow vertices of degree 2 (and not

faces of degree 2) you can build examples for instance

with 6 vertices and 4 faces: one square with two triangles

added at two neighboring sides.

Tasmanian Devil proposed:

> There is the program "plantri" available online that generates

> planar graphs. A good C-programmer could modify it to search

> for alternating planar graphs.

Thanks for the hint.

Ingo.

New record holder is Frank Schneider,

the chess programmer. His solution (by

computer search) has 17 vertices and 17

faces. See under

http://f23.parsimony.net/forum50826/messages/178269.htm

Ingo.

In view of Euler's formula, maybe it is more elegant to ask for the minimal value of the number of edges than for the number of vertices plus the number of faces?

Minimizing the number of vertices and minimizing the number of faces are of course dual problems.

So we could ask for alternating graphs with the minimal number of vertices or the minimal number of edges.

Is there an infinite alternating graph?

Is there an infinite alternating graph where each vertex has degree 3, 4 or 5 and each face has 3, 4 or 5 sides?

Are there infinitely many alternating graphs where each vertex has degree 3, 4 or 5 and each face has 3, 4 or 5 sides? Do they become more and more numerous as we increase the total number of vertices?

"Is there an infinite alternating graph?" The question doesn't quite make sense to me because you have to deal with regions with infinitely many sides. Here is a construction of arbitrarily large alternating graphs: take your beautiful pentagon above, and label the top left hand vertex A, and then go clockwise A,B,C,D,E labelling the outer vertices. Now glue BC for one pentagon to ED for another [so you have vertices of degrees 6 and 8 in the new construction]. Make a chain of 100 pentagons that way; if I've got it right this will give rise to a large alternating graph. I leave it to you to decide whether the "limit" of this construction is alternating.

Clarification! Glue B to D and C to E!

Yep, I guess that works! Thanks!

I studied the drawing and found a more symmetric representation that I will post shortly.

Your concern about faces with infinitely many sides is supporting argument for my "3-4-5"-restrictions above. :-)

*a* supporting argument even

That looks fantastic, you Tasmanian Devil, you!

Thanks a lot for the drawings.

It is a pity that I have to do administration work

the whole night now...

Ingo.

I am no completely sure, but it seems to

me that the graph of Frank Schneider is

self-dual.

Ingo.

Amazing work, Jan! Bravo!

Thanks, but there was nothing to it, just recreation.

Yours isn't isomorphic to Frank's, so I wonder how many solutions there are.

Um, yes it is, I haven't found any on my own.

@phil: he's moved the point at infinity. I find that considering the pentagons helps me orient myself.

Doh! One of these days I'll learn to count up to 4!

So bravo Frank! Tas - you're nearly as useless as I am :-P

I know - don't tell the principal.

Tasmanian Devil wrote:

> Thanks, but there was nothing to it, just recreation.

Thanks again for the nice drawings. I had such a good

sleep with the knowledge that the graph is so beautiful.

Question: How did you generate the drawings?

By hand ,

or fully automatically (with what software?),

or computer-aided in some way?

Best regards, Ingo

I drew it on paper looking at Frank's definition, then drew it with Paint, then noticed the symmetry of the quadrangles, re-drew it several times on paper, then drew it with Paint again.

I believe I have a proof that for alternating graphs for which all vertices have degree 3, 4 or 5, and all faces have 3, 4 or 5 sides, the number of vertices must be equal to the number of faces. This is not true for alternating graphs in general (in view of wccanard's construction). I can post the proof if you like.

paint? that's really low-tech! :P

> I drew it on paper looking at Frank's definition,

> then drew it with Paint, then noticed the

> symmetry of the quadrangles, re-drew it several

> times on paper, then drew it with Paint again.

Thx. Before your pictures came, I had the idea to enter

the graph into computer geometry software Cinderella

(which allows vertices to be moved around, all connections

simply following).

> I believe I have a proof that for alternating graphs

> for which all vertices have degree 3, 4 or 5, and all

> faces have 3, 4 or 5 sides, the number of vertices

> must be equal to the number of faces.

That sounds interesting.

Please, post it.

> This is not true for alternating graphs in general (in

> view of wccanard's construction).

And it is also not true for arbitrary planar graphs with

restrictions 3, 4, 5 for vertices and faces.

Ingo.

Gregorio:

> paint? that's really low-tech! :P

lowtech or not - paint is fantastic. You can

manipulate each single pixel very easily.

paint is my first choice when doing graphics.

Ingo

I'll remark that my construction (glueing pentagons together) produces graphs with different numbers of vertices than faces, but some vertices have degree 8. On the other hand the original example of an alternating graph has vertices and faces of degree 6 but also the same number of vertices as faces. Can you squeeze 6 into your proof Tasmanian Devil?

We call a graph (3,4,5)-alternating if it satisfies the following conditions:

-it is planar

-each vertex has degree 3, 4 or 5

-each face has 3, 4 or 5 sides

-any two adjacent vertices have different degree

-any two adjacent faces have different number of sides

Theorem: If G is a (3,4,5)-alternating graph, then the number of vertices of G is equal to the number of faces of G.

Proof: Suppose G is a (3,4,5)-alternating graph. Let vi denote the number of vertices of degree i, and let fj denote the number of faces with j sides.

Summing the edges over the vertices shows that the total number of edges is (3v3+4v4+5v5)/2, while summing over the faces shows that it is (3f3+4f4+5f5)/2. So we have

(1) (3v3+4v4+5v5)/2 = (3f3+4f4+5f5)/2

Euler's formula gives

2(v3+v4+v5) + 2(f3+f4+f5) = (3v3+4v4+5v5)/2 + (3f3+4f4+5f5)/2

which simplifies to

(2) v3 + f3 = v5 + f5 + 8

The rest of the proof is based on counting (i, j)-combinations, that is, the number of instances of a vertex of degree i belonging to a face with j sides. For example, each vertex of degree 3 must belong to a triangle, a quadrangle and a pentagon, and eacg triangle must have one vertex of each degree (3, 4 and 5). So we see that the number of (3, 3)-combinations must be equal to v3, but it must also be equal to f3, so we can deduce that

(3) v3 = f3

Counting (3, 5)-combinations show that

(4) f5 <= v3

while a dual argument (counting (5, 3)-combinations) shows that

(5) v5 <= f3

Combining (1), (2), (3), (4) and (5) gives us five possibilities:

v5 = v3 - 8, f5 = v3

v5 = v3 - 6, f5 = v3 - 2

v5 = v3 - 4, f5 = v3 - 4

v5 = v3 - 2, f5 = v3 - 6

v5 = v3, f5 = v3 - 8

Let ai denote the number of vertices of degree 5 that belong to exactly one face with i sides (and two of each of the other two types). Counting (5, 3)-combinations shows that

a3 = 2v5 - v3, a4 + a5 = v3 - v5

The number of (5, 5)-combinations is a5 + 2(v5 - a5) = 2v5 - a5. A dual argument show that it is also equal to 2f5 - b5 where bj denotes the number of pentagons with exactly one vertex of degree j. So we have

(6) a5 - b5 = 2(v5 - f5)

But since 0 <= a5 <= v3 - v5 and 0 <= b5 <= f3 - f5, this is only possible if v5 = f5 = v3 - 4. In particular, if v5 = v3 - 2 or v5 = v3, a5 is at most 2, making (6) impossible. If v5 = v3 - 6 or v5 = v3 - 8, we can look at b5 instead: it is at most 2, again making (6) impossible. Of course, (1) now also gives v4 = f4 and the result follows.

wccanard, I am afraid the argument falls apart if I try to include 6.

Gregorio: I know, I also use Turbo Pascal 4.0 to explore mathematical problems. :p

There is a "+ 4" missing in Euler's formula

Another remark: let's say the "degree" of an alt. graph is the max of the degrees of the vertices and the sides of the faces. By definition the degrees of vertices and sides of faces all must be 3 or more, so T.Devil is talking about alternating graphs of degree 5. TD says that they always have the same number of vertices as faces. Are deg 5 alternating graphs always self-dual??

(6) a5 - b5 = 2(v5 - f5)

Hoorah - I am now officially (OK, that's also self-appointed) the single most useless contributor to this thread!

@Tas: very nice! You in fact prove that v_n=f_n for n=3,4,5, which is further evidence for the question as to whether they're always self-dual. I didn't even check whether the 17-example was self-dual though.

Yes, Frank's graph is self-dual, but I think it is too early to guess that this is always the case.

I tried to work out how big v4 would be compared to the others and it seems to be between 3v5/4 and v3/2 + v5 (don't take my word for it though).

phil, my usefulness is approximately equals to your4s ;)

@ingo: i was being ironic :)

Tasman-Jan,

thx for presenting the proof. This evening, in the train

home to family, I will hopefully find time to

go through it step by step.

\*\*\***********************

@Gregorio:

> i was being ironic :)

Good hint. But believe me or not: there are crowds

of people out who really believe that old software

can not be good.

Ingo.

I should mention that (1) and (3) gives that v5 - f5 must be divisible by 4.

@ingo: being low-tech is not necesarily a bad thing :)

Tasmanian Devil wrote:

> I should mention that (1) and (3) gives

> that v5 - f5 must be divisible by 4.

Hmm, a joke?

In your proof one of the statements is v5 = f5.

In the train, I checked the proof. At the end,

it took me some time to verify the steps, but

all is ok.

Maybe it would be a more natural formulation to state

in the theorem that

v3=f3, v4=f4, and v5=f5;

and only as a corollary that number of vertices = number of faces.

A conjecture:

Let p(i,j) be the number of (i,j)-combinations.

Then it might hold that

p(i,j) = p(j,i) for all i,j in 3,4,5.

If true, this would be one more small step

in direction of self-duality.

And a bold open question:

Is it true that every (3,4,5)-alternating graph is not

only self-dual, but also antipodal?

(Meaning of "antipodal": You can span the graph

on a sphere in such a way, that on the opposite side of

each vertex with arbitrary degree k there is a face with

k sides.)

The Schneider graph is antipodal.

Ingo

> I should mention that (1) and (3) gives

> that v5 - f5 must be divisible by 4.

> Hmm, a joke?

> In your proof one of the statements is v5 = f5.

He he, true...but I meant that it should be inserted into the proof when I get only 5 cases and not v5 = v3 - 7, f5 = v3 - 1 and so on. Alternatively, the last step that narrows it down to one case also works without applying this result.

> In the train, I checked the proof. At the end,

> it took me some time to verify the steps, but

> all is ok.

Good - maybe we will see an update of your web page soon? ;-)

My web page on alternating planar graphs

is updated. Watch at

http://www.althofer.de/alternating-planar-graphs.html

and/or have a nice weekend.

Ingo.