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?

  • 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?2012-09-06
  • 0
    @ThomasAndrews Here is an example of a nice graph that is not a triangulation of the sphere: http://www.graphclasses.org/images/g_co-3K2.gif.2012-09-06
  • 0
    @AustinMohr Isn't that just the octahedron graph? That looks clearly like a triangulation of a sphere.2012-09-06
  • 0
    @ThomasAndrews You are correct.2012-09-06
  • 0
    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.2012-09-07
  • 0
    @ThomasAndrews That is really helpful. Any ideas about how one would go about doing that?2012-09-07
  • 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...

  • 0
    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?2012-09-07
  • 0
    Actually, I think there is an error in my proof - I think there are triangulations of the sphere that are not "nice."2012-09-07
  • 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