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.
Best,
-Yan
 A: Wow. Scary how I've failed to do this until I ask the question on MO, and then immediately get the idea.
Here's a proof, assuming the weaker version of the theorem is true:
Call such an ordering "good." Consider a minimal counterexample $M$ of size $n$ to our stronger claim: it must be chordal, has a good ordering, but does not have a good ordering starting at every vertex. However, every chordal graph of size less than $n$ has a good ordering starting at every vertex.
Since $M$ has some good ordering $T$, it has some vertex $v$ (the last one in $T$) such that all its neighbors form a clique. Remove this vertex to get $M'$. $M'$ is chordal (since chordality respects vertex deletion), so we can make a good ordering starting with any element in $M'$. Attach $v$ to the end. This ordering is obviously still good. Thus, we can make a good ordering starting with any vertex that is not $v$. So it suffices to make a good ordering starting with $v$.
To do this, consider the last vertex $w$ in $T \setminus v$ with the property that $w$ is not connected to the vertex $w'$ immediately following it in $T$. If $w$ doesn't exist, this just means $M$ is a clique, so any ordering is good and we have a good ordering starting with $v$. If $w$ exists, then notice that $w$ cannot be connected with any of the vertices after it in $T$; if it is, then pick the earliest such one $u \neq w'$, which is both connected to the vertex directly preceding it (not connected to $w$ by choice of $u$) and $w$, a contradiction on the ordering being good. Thus, $w$ is only connected with vertices preceding it. This means all of $w$'s neighbors form a clique. Hence, we can delete $w$, make a good ordering starting with $v$ of the rest, and append $w$ to the end. A winner is us.
-Yan
A: It's known/obvious from the next few lines of the Wikipedia article stating that a LexBFS ordering (or its reverse, depending on your conventions) gives a perfect elimination ordering, since LexBFS can be made to start at any vertex.
