# Graph for which certain induced subgraphs are cycles

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?

-
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

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...

-
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
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