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"