2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Leen Droogendijk Sep 20 '16 at 10:40
  • $\begingroup$ @LeenDroogendijk : sorry I will fix this and thanks $\endgroup$ – kroner Sep 20 '16 at 10:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Shagnik Sep 20 '16 at 10:45
  • 1
    $\begingroup$ @Shagnik : thanks tried to fix this hope it is better now $\endgroup$ – kroner Sep 20 '16 at 10:46
  • 1
    $\begingroup$ I edited it a bit more - feel free to change it back if you don't agree. $\endgroup$ – Shagnik Sep 20 '16 at 12:06
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ You're very welcome! $\endgroup$ – Shagnik Sep 20 '16 at 15:10

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.