From: rld@math.ohio-state.edu (Randall Dougherty)
Subject: Re: planar graphs and first-order definability
Date: 1 Sep 1999 18:56:54 GMT
Newsgroups: sci.math
In article <37CD33A0.97BF2DDC@eil.utoronto.ca>,
Michael Gruninger wrote:
>Is the class of planar graphs first-order definable?
No, it isn't. One way to see this is to look at the "strip"
graphs S_n and M_n which both look like
u_1 ----- u_2 ----- u_3 ----- . . . ----- u_n
| | | |
| | | . . . |
| | | |
v_1 ----- v_2 ----- v_3 ----- . . . ----- v_n
except that S_n has additional edges from u_n to u_1 and from v_n to v_1
(forming an ordinary closed strip) while
M_n has additional edges from u_n to v_1 and from v_n to u_1
(forming a Moebius strip). So S_n is planar but (for n >= 3) M_n is not.
It is not hard to show that, if n > 2^k, then the second player wins
the k-move Ehrenfeucht-Fraisse game for S_n and M_n; this means that
a first-order sentence with k quantifiers cannot distinguish S_n from M_n.
Hence, no first-order sentence can distinguish all planar graphs from all
nonplanar graphs.
Randall Dougherty rld@math.ohio-state.edu
Department of Mathematics, Ohio State University, Columbus, OH 43210 USA
"I have yet to see any problem, however complicated, that when looked at in the
right way didn't become still more complicated." Poul Anderson, "Call Me Joe"