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.

Let us call a graph G $nice$ if for any vertex $v \in G$, the induced subgraph on the vertices adjacent to $v$ is exactly a cycle.

Is there anything that we can conclude about nice graphs? In particular, can we find a different (maybe simpler) but equivalent formulation for niceness?

share|improve this question
1  
Certainly, any triangulation of the sphere would satisfy this condition. Are there any such graphs which cannot be represented as a triangulation of the sphere? –  Thomas Andrews Sep 6 '12 at 16:59
    
@ThomasAndrews Here is an example of a nice graph that is not a triangulation of the sphere: graphclasses.org/images/g_co-3K2.gif. –  Austin Mohr Sep 6 '12 at 20:17
    
@AustinMohr Isn't that just the octahedron graph? That looks clearly like a triangulation of a sphere. –  Thomas Andrews Sep 6 '12 at 20:46
    
@ThomasAndrews You are correct. –  Austin Mohr Sep 6 '12 at 23:59
    
I think there are non-sphere examples, such as triangulations of a torus. I do think that you can show that a finite "nice" graph that is a triangulation of some compact 2-dimensional manifold. –  Thomas Andrews Sep 7 '12 at 1:36

1 Answer 1

Wrong Answer

Given a finite connected "nice" graph, $G$, you can take all triples $\{a,b,c\}$ of nodes with $\{a,b\}$,$\{b,c\}$, and $\{a,c\}$ edges in the graph.

Take these as $2$-simplexes, and stitch them together in the obvious way.

The fact that $G$ is nice means that each edge must be on exactly two triangles. The fact that $G$ is nice also means that the interior of the union of the triangles that contain node $a$ will be homeomorphic to an open ball in $\mathbb R^2$.

So this all shows that stitching these together will yield $G$ as a triangulation of a compact $2$-manifold.

There is at least one "degenerate" case for which this is not true - the single-edge graph with two nodes. Depends on whether you consider a single node graph to be a cycle...

share|improve this answer
    
I wouldn't consider either $K_1$ or $K_2$ to be cycles, so I think this is exactly right. Question: does this imply that any planar nice graph is a triangulation of the sphere? –  yrudoy Sep 7 '12 at 14:42
    
Actually, I think there is an error in my proof - I think there are triangulations of the sphere that are not "nice." –  Thomas Andrews Sep 7 '12 at 16:05
1  
Take the graph of two tetrahedrons with one face glued together. Then the "glued" nodes are neighbors of every other node, but removing one of the glued nodes yields a non-cyclic graph. It's also true tht if you take all the triangles of this graph, they don't make a $2$-manifold, so both sides of my argument are wrong. –  Thomas Andrews Sep 7 '12 at 16:11

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.