4
$\begingroup$

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?

  • 0
    The outline of the proof is to realize the triangles by taking a point and its neighbors. Since there is a loop amongst the neighbors, that gives you a set of triangles, and the interior of these triangles, when stitched together appropriately, become a 2D neighborhood. So you can basically stitch together a bunch of triangles to get a 2-manifold.2012-09-07

1 Answers 1

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

  • 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.2012-09-07