Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have an infinite graph $G$. I assume $G$ to be cubic and planar. No further conditions, so it will be irregular, maybe in the sense of cubic planar version of Rado's graph: Every possible combination of faces exists somewhere in this graph (like in normal numbers).

Now you are given a second one of such a graph $G'$. They might look different at first glance, but aren't they actually identical?

share|improve this question
1  
In simple words, you are asking whether or not the theory of cubic and planar graphs with the requirement that the graph is infinite is $\aleph_0$ categorical? –  Asaf Karagila Nov 24 '13 at 21:57
    
@Asaf hmm, I think so: Yes...is it? –  draks ... Nov 24 '13 at 21:58
    
I don't know... If "just cubic and planar" imply random (in the sense of Rado graph) then yes. –  Asaf Karagila Nov 24 '13 at 22:01
    
@Asaf What else could? So and do you mean that $G$ is the planar cubic subgraph of Rado's graph? –  draks ... Nov 24 '13 at 22:04
1  
I think that I don't know enough terminology in graph theory to give a comprehensive answer (otherwise I would have), and I trust Brian enough to be certain of his knowledge of graph theory. I'd go and fiddle around the definitions, but all my brain resources have been allocated to four problems as it is... :-) –  Asaf Karagila Nov 24 '13 at 22:33

1 Answer 1

These are not isomorphic: the second has bridges, and the first has none.

          --o----o----o----o--  
            |    |    |    |  
          --o----o----o----o--

            o          o          o  
           /|\        /|\        /|\  
          / | \      / | \      / | \  
       --o  |  o----o  |  o----o  |  o--  
          \ | /      \ | /      \ | /  
           \|/        \|/        \|/  
            0          o          o
share|improve this answer
    
...that's not what I thought about. I meant something random like Rado's graph (see Asaf's comment above). –  draks ... Nov 24 '13 at 22:07
    
@draks...: They’re cubic planar graphs. Perhaps you need to add some conditions? –  Brian M. Scott Nov 24 '13 at 22:07
    
Yes they are. Formally you're right: It answer what I've written, but it doesn't answer what I thought. Thanks anyway... –  draks ... Nov 24 '13 at 22:09
    
@draks...: You’re welcome. I now have a general idea of what you had in mind, but I don’t immediately see how to make it precise. –  Brian M. Scott Nov 24 '13 at 22:10
1  
Does this work? How could such a graph even contain $K_4$? –  draks ... Nov 24 '13 at 22:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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