characterization of chordal graphs
I recently tried to prove the following characterization of chordal graphs, attributed to Fulkerson & Gross:
"A graph $G$ is chordal if and only if it has an ordering such that for all $v \in G$, all the neighbors of $v$ that precede it in the ordering form a clique."
I believe the wikipedia page calls this (or its reverse) a "perfect elimination ordering." In any case, my proof was harder than I expected and I ended up with the following strengthening:
"$G$ is chordal if and only if for any $v \in G$, we can find such an ordering of $G$ that starts with $v$."
I would like to know if this strengthening is:
1) known / obvious from the weaker theorem / obvious from folklore, or 2) wrong. =)
I can of course give a proof to anyone who is interested - it is just too long to fit here.