# Is the Wikipedia article about chordal graphs incorrect?

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.

• $K_3$ is in fact chordal. Every cycle of length greater than 3 (none) has a chord (true) – Jernej Apr 10 '16 at 8:03
• 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. – adamcatto Apr 10 '16 at 22:54

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.
• 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? – adamcatto Apr 10 '16 at 0:57
• 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). – Josse van Dobben de Bruyn Apr 10 '16 at 1:00