Chordal graphs and perfect elimination orderings

[mathgirl1]

1. G is chordal iff G has a Perfect Elimination Scheme/Ordering (PES)
2. G is chordal iff every induced subgraph H of G has a simplicial vertex in H.

I want to show directly (ie, don't use the above) to show that G has a PES iff every induced subgraph H of G has a simplicial vertex.

(->) Assume G has \(\displaystyle PES = [v_1, v_2, ..., v_n]\) By definition every \(\displaystyle v_i\) is simplicial in the graph \(\displaystyle H=G[v_i, v_{i+1}, ... v_n]\) (ie H = the graph induced by the vertices \(\displaystyle v_i, v_{i+1}, ... ,v_n\) in G). I need to show that given any subset of PES, say \(\displaystyle H = G[x_1, x_2, ..., x_m] \) that this graph has a simplicial vertex. I'm pretty sure that this needs to be done BWOC. If each graph didn't have a simplicial vertex then there wouldn't be a PES ordering. But I'm not exactly sure how to show this. It seems so simple and direct and I'm stuck. I guess I need the why this is true and I'm missing it. But anyway, I would assume there exists an induced subgraph H that doesn't have a simplicial vertex, then there wouldn't be a PES for this particular subgraph. But how do I extend that to say there wouldn't be a PES for all of G?

(<-) Assume every induced subgraph H of G has a simplicial vertex and show that G has a PES. Again, I'm pretty sure to do this by contradiction but it seems too simple to say that if each subgraph has a simplicial vertex and but G doesn't have a PES then this contradicts that each subgraph has simplicial vertex. This direction may actually be this easy but I still feel like I'm missing something simply obvious. I know there has to be more bulk to this proof! Help! I'm going in circles and getting no where.

Any help is appreciated! Thank you so much! I typically struggle with the simple (and probably obvious) ones.

 

[Valkarie]

A:(->) Assume $G$ has PES = [v_1, v_2, ..., v_n]. We need to show that given any subset of PES, say $H = G[x_1, x_2, ..., x_m]$, this graph has a simplicial vertex. Let $H=G[x_1, x_2, ..., x_m]$ be an induced subgraph of $G$. Since $G$ has PES, there exists some $i$ such that $x_1,x_2,...,x_m \in \{v_i,v_{i+1},...,v_n\}$. That is, there is some $v_j$ in the PES of $G$ that is also in $H$. Since $v_j$ is simplicial in $G$, then it is also simplicial in $H$. Therefore, every induced subgraph of $G$ has a simplicial vertex.(<-) Assume every induced subgraph $H$ of $G$ has a simplicial vertex. We need to show that $G$ has a PES. We will prove this by induction on the number of vertices in $G$.Base Case: Let $G$ be a graph with one vertex, $v$. Then $G$ has an empty set of edges and so $v$ is a simplicial vertex. Thus, $G$ has a PES consisting of just $v$.Inductive Step: Let $G$ be a graph with $n$ vertices and suppose that every graph with $n-1$ vertices has a PES. Let $u$ be a simplicial vertex in $G$. Then $G\backslash u$ has $n-1$ vertices and so by the inductive hypothesis, $G\backslash u$ has a PES, say $P=\{v_1,v_2,...,v_{n-1}\}$. Then $P \cup \{u\}$ is a PES for $G$. Thus, $G$ has a PES. Therefore, by induction, every graph $G$ has a PES.