I was working with chordal graphs and the connection to the cycle space, i.e. the $\mathbb{F}_2$-vectorspace on the set of all edges with the fundamental cycles as a basis.
I initially thought that any cycle that is generated by triangles in the cycle space is chordal. However, this is certainly not true. Take a wheel (a vertex with a (chordless) cycle in its neighbourhood).
Now I was wondering if that is the only obstruction in the sense that if we forbid such wheels as induced subgraphs then every cycle that is generated by triangles is chordal.
I'd appreciate any kind of insight!
Best Answer
This is a very interesting question! Here's my crack at it (also, an unstated assumption is that there's at most one edge between two vertices):
Let $G$ be a graph for which this statement is false, and let $C = T_1 + T_2 + \ldots + T_n$ be the cycle in question. Well, assuming $C$ is not just a triange, to fulfill the chordless requirement, there has to be at least one vertex $x$ that is a part of some $T_i$, but not of $C$. Now, let $I$ be the set of all $i$ for which $x$ is a vertex in $T_i$.
Take some $T_i$ with $i \in I$, and let $E$ be an edge of it connected to $x$. Since $E$ is not an edge in $C$, there has to be at least one $j \in I$ such that $i \neq j$ and $E$ is an edge of $T_j$. Well, if we repeat this process with the other edge connected to $x$ of $T_j$, we'll get some triangle $T_k$ and so on. Eventually we will have to loop around at some point, which creates a wheel with center $x$.
Edit: I just realized this proof needs a small amendment. I have successfully proven (I think) that our graph $G$ must contain a wheel as a subgraph, but not as an induced subgraph. Luckily, this is only a slight hinderance: if you add an extra edge to a wheel somewhere, it's easy to see that you can remove some verticies to get a smaller wheel.