# Proving chordal graph has unique maximal clique

In my studies of graph theory I recently came across the following:

Let $$G$$ be a finite simple undirected graph which is chordal and for some $$e \in E(G)$$ the graph $$G-e$$ is also chordal then there exists a unique maximal clique $$K$$ in $$G$$ such that both ends of $$e$$ are in $$K$$.

A finite simple undirected graph is chordal if every cycle of length greater than three has a chord . Equivalently, a graph is chordal if it has no induced cycle of length greater than three.

A useful theorem I thought might help here

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.

I cannot seem to relate the graph being chordal and the modified graph being chordal to the existence of any clique, let alone to a unique one with both ends of $$e$$ are in this clique. I thought perhaps perfect elimination order would be a clue here but I cannot proceed any further. I certainly appreciate all help.

• The use of "is also chordal" in the problem statement suggests that $G$ is supposed to be chordal. If this is intended you need to state it explicitly. Sep 20 '16 at 10:40
• @LeenDroogendijk : sorry I will fix this and thanks Sep 20 '16 at 10:41
• Your definition of a chordal graph seems to be a little off: every cycle should have a chord or, equivalently, there are no induced cycles of length greater than three. Sep 20 '16 at 10:45
• @Shagnik : thanks tried to fix this hope it is better now Sep 20 '16 at 10:46
• I edited it a bit more - feel free to change it back if you don't agree. Sep 20 '16 at 12:06

I don't think you need to use the theorem for this - you can prove the result by contradiction. (I also don't think we need $G$ to be chordal.)

Suppose that there is an edge $e = \{u, v\}$ such that both $G$ and $G - e$ are chordal, and that there are two maximal cliques, say $M_1$ and $M_2$, both containing $\{u,v\}$. Now try to use these cliques to construct a cycle that will not have a chord in $G - e$. Details are behind the spoiler below.

As $M_1$ is a maximal clique, we must have a vertex $x \in M_1 \setminus M_2$, since otherwise $M_1 \subset M_2$. Now there must be a vertex $y \in M_2$ such that $\{ x, y \} \notin E(G)$, as otherwise $M_2 \cup \{ x \}$ would be a larger clique, contradicting the maximality of $M_2$.

Continuing the solution below.

Since $\{u, v\} \subset M_1 \cap M_2$, it follows that each of $x$ and $y$ is adjacent to both of $u$ and $v$. Hence we have the $4$-cycle $(x,u,y,v)$. Since $x$ is not adjacent to $y$, this cycle does not have a chord in $G - e$, which is a contradiction. Hence there must be a unique maximal clique containing both $u$ and $v$, as required.

Note that we actually proved a stronger statement. If in a simple graph $G$ there is an edge $e$ such that $G - e$ does not contain an induced $C_4$, then there is a unique maximal clique containing both endpoints of $e$.

• You're very welcome! Sep 20 '16 at 15:10