A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.
I'm not sure whether the concept of maximal chordal graphs exists. I tentatively define it as follows:
- A chordal graph is maximal if adding an edge between any two non-adjacent vertices makes the graph non-chordal or non-simple.
According to the definition, complete graphs meet the requirements, but are there any others besides complete graphs?
Sometimes induced cycles that are not triangles are called "holes". That is to say, adding any edge will create a hole. Do such chordal graphs (but not complete graphs) exist?
Note: If such non-complete chordal graphs do not exist, then starting from any chordal graph, we can continually add edges (while maintaining its chordal property) until it becomes a complete graph.
I tested chordal graphs with at most 10 vertices one by one using a computer and did not find a desired maximal chordal graph.
Best Answer
Complete graphs are the only chordal graphs with the property that adding any non-edge creates a hole.
Let $G$ be such a graph. Let $k \geq 0$ be the largest so that there exists $x, y, z_1, \dots, z_k \in V(G)$ forming an induced $K_{k+2}-e$ in $G$ with $xy$ as the missing edge. Since $xy$ is a non-edge, adding $xy$ would create a hole $x w_1 \dots w_\ell y$ with $\ell \geq 2$. Notice that the $w_i$ are distinct from the $z_i$, as otherwise there would be a chord in this hole. Since $x w_1 \dots w_\ell y z_i$ is a cycle in $G$, but there are no edges among $x, w_1, \dots w_\ell, y$ other than those in the cycle, we have that every $z_i$ is adjacent to every $w_j$. Since $x$ is not adjacent to $w_2$, we have that $x, w_2, z_1, \dots, z_k, w_1$ forms an induced $K_{k+3}-e$ with $xw_2$ as the missing edge, contradicting the maximality of $k$.
Thus $G$ has no induced $K_2-e$, that is, every pair of vertices in $G$ are adjacent.