# Is a rigid cycle a chordal graph?

There are two relevant questions:

(1) We know an edge set $C$ is a rigid cycle in $\mathcal{G}_2(n)$ if and only if $|E(C)|=2|V(C)|−2$ and $|F|≤2|V(F)|−3$ for every proper subset $F$ of $E(C)$. Thus, I want to know: Is a rigid cycle a chordal graph? (It can be found in Wiki that chordal graphs are also called as "rigid circuit graphs". But i can't find the connection between it and rigid cycle. Are they the same thing?)

(2) A graph $G=(V,E)$ is defined as pseudocycle iff $|E|=2|V|−2$ and $F\leq 2|V(F)|−2$, $\forall \ \emptyset\subset F\subset E$. Thus, I also would like to know: Is a pseudocycle a chordal graph?

Thanks very much!

• What does G2(n) mean? – Gerry Myerson Oct 16 '14 at 22:06
• No to the second question, as exhibited by a graph on five vertices and eight edges with minimum degree 3. – Andrew D. King Oct 16 '14 at 23:32
• These definitions comes from the book Combinatorial Rigidity by Jack Graver, Brigitte Servatius and Herman Servatius. In their book, $\mathcal{G}_2(n)$ is the unique maximal 2-dimensional abstract rigidity matroid on n vertices. It would be OK if just thinking the graph C satisfies the condition. And I just want to know whether such a C is chordal or not. Thanks! – Mark Oct 17 '14 at 12:17
• @Andrew, thanks a lot! Actually, my previous intuition is the same as yours. But what I am most interested in the elimination order (not necessarily perfect) of certain graph (so-called pseudocycle) formed by the union of two spanning trees. The elimination order I mean is the order of vertices according to which I delete each vertex and add edges between the remaining vertices incident to the deleted vertex (if there is no edge between those incident vertices). The elimination order I want to find in the pseudocycle is the order that allowes me to add at most $O(n)$ extra edges totally. – Mark Oct 17 '14 at 12:44