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 of H.
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
![PES = [v_1, v_2, ..., v_n]](/CBB/latexrender/pictures/0362e4a0b1741502582c3a0715feea08.png "PES = [v_1, v_2, ..., v_n]")
By definition every
is simplicial in the graph
![H=G[v_i, v_{i+1}, ... v_n]](/CBB/latexrender/pictures/552c859855168010a3e55b783ff83bb9.png "H=G[v_i, v_{i+1}, ... v_n]")
(ie H = the graph induced by the vertices
in G). I need to show that given any subset of PES, say
![H = G[x_1, x_2, ..., x_m]](/CBB/latexrender/pictures/3ebf23a1e4e8ff6fbd16b9cdf937ac60.png "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.
(<-) Assume every induced subgraph H of G has a simplicial vertex then 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 didn't have a simplicial vertex then there wouldn't be a PES ordering. Which would be the same proof as the (->) part. I guess I'm missing the how this happens because it seems so direct from definition. I'm going in circles!
Any help is appreciated! Thank you so much!
Login
FAQ
Search
