0
$\begingroup$

Give a tree graph $T_1$ =$(V,E)$ how can we prove that it has a Perfect Elimination Scheme :P.E.S

P.E.S : is an ordering of the vertices, in such away that a vertex $v_i$ is simplical in the induced graph G on all vertices.

$\endgroup$
2
  • 3
    $\begingroup$ Find a leaf. Remove it. Repeat. $\endgroup$ Commented Jan 21, 2016 at 21:54
  • $\begingroup$ Does every node in a Tree build a clique ? $\endgroup$ Commented Jan 21, 2016 at 22:03

1 Answer 1

1
$\begingroup$

Assuming $ T = (V,E) $ is a finite tree, it has exactly $ \left|V\right|-1 $ edges. It's easy to show that if $ \left|V\right|>1 $ then there exists a vertex with degree 1 (otherwise there would be too many edges, or the tree wouldn't be connected). Such a vertex is called a leaf. If we remove a leaf, the resulting graph is still a tree, since we are neither disconnecting our tree nor creating a cycle.

Thus, we can keep removing these leaf vertices, getting back a tree each time, until we're left with one vertex. Since a leaf has degree 1, it is trivially a clique with its neighbours.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .