0
$\begingroup$

This is the wiki for chordal graphs. It states that "A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that occur after v in the order form a clique. A graph is chordal if and only if it has a perfect elimination ordering.", but chordal graphs are only defined over the set of cyclic graphs with more than 3 vertices. Should this article be updated to "A graph is chordal if and only if it has a perfect elimination ordering and has more than 3 vertices"? Without the second constraint, we can consider $K_3$ to be chordal, but it is not chordal.

$\endgroup$
  • $\begingroup$ $K_3$ is in fact chordal. Every cycle of length greater than 3 (none) has a chord (true) $\endgroup$ – Jernej Apr 10 '16 at 8:03
  • $\begingroup$ Yep, I made a mistake in the logic. I thought it was: IF a graph is chordal, THEN Every cycle of length greater than 3 has a chord AND there exists a cycle of length greater than 3. Didn't realize that the "there exists..." portion wasn't necessary. $\endgroup$ – acatto Apr 10 '16 at 22:54
1
$\begingroup$

Let us look more closely at the definition of chordal graphs:

Definition. A graph $G = (V,E)$ is said to be chordal if every cycle of length $\geq 4$ has a chord. (Equivalently: it has no induced cycles of length four or more.)

Since $K_3$ does not have any cycle of length $\geq 4$, it is trivially chordal. Similarly, any tree is trivially chordal, for it does not have any cycles at all.

$\endgroup$
  • $\begingroup$ The definition I've seen is in the first sentence of the wiki article, which I posted as the first sentence of the description. A chord is defined as an edge that is not part of the cycle, but connects two vertices on the cycle. In $K_3$, all edges are part of the cycle, so there can't be a chord. I guess it's a matter of semantics of the term "Chordal Graph"; i figured that chordal graphs must have a chord on them, but this means that $K_3$ is trivially chordal? $\endgroup$ – acatto Apr 10 '16 at 0:57
  • 1
    $\begingroup$ Ah, but the requirement is only for cycles of four or more vertices. Since $K_3$ has no cycles of length $4$ or more, it is trivially chordal. Similarly, any tree is chordal, for it doesn't have any cycles at all (let alone cycles of length $4$ or more). $\endgroup$ – Josse van Dobben de Bruyn Apr 10 '16 at 1:00
  • $\begingroup$ Ah, ok, I figured. At first I thought that 4 or more vertices was a necessary condition, which is where the confusion stemmed from. Thanks for clearing that up! $\endgroup$ – acatto Apr 10 '16 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.