Clique numbers of chordal graphs

Question

Let $c_i$ be the number of complete subgraphs of size $i$ in a graph $G$. I learned the following result:

If $G$ has $n$ vertices and is connected and chordal, that is, $G$ does not have induced cycles of length at least 4, then $$ \sum_{i=1}^n (-1)^{i+1} c_i = 1 $$

See for example Thm 4.1 (together with the fact that $\lambda=1$ is a root after Theorem 3.1) in this paper, or Prop 2.3 of this paper.

My question is the following:

1. Is there an elementary proof of this fact without resorting to topological arguments?

2. Is there a generalization of this to k-chordal graphs?

Answer 1

Here is another argument. A chordal graph has a perfect elimination ordering $v_1,\dots,v_n$ of its vertices. This means that the neighbors among $v_1,\dots,v_{i-1}$ of $v_i$ form a clique $C_i$ . See for instance https://en.wikipedia.org/wiki/Chordal_graph. If $C_i$ has $p_i$ vertices, then we obtain ${p_i\choose j}$ new cliques of size $j+1$ when we adjoin the vertex $v_i$ to the subgraph spanned by $v_1,\dots,v_{i-1}$. If $G$ is connected then $p_i>0$ when $i>1$, so $\sum (-1)^{j}{p_i\choose j}=0$. Hence the sum $\sum_{i=1}^n (-1)^{i+1}c_i$ is equal to the contribution from adjoining the first vertex $v_1$, namely, 1.

Answer 2

Let's prove that in a chordal graph we have $s(G):=c_1-c_2+c_3-\dots=c_0$, where $c_0$ denotes the number of connected components. Assume the contrary and let $G$ be a minimal (in the sense of number of vertices) counterexample. Then $G$ is connected and has at least two vertices. Let $v$ be such a vertex that $G-v$ is connected. The key fact is that the graph induced on the 1-neighborhood $N(v)$ is also connected. Indeed, if $N(v)=A\sqcup B$ with non-empty $A,B$ and there are no edges between $A$ and $B$, then consider the minimal path in $G-v$ from some $a\in A$ to $b\in B$. Adding the edges $va,vb$ to this path we get a chordless cycle. Well, now $s(G)=s(G-v)-s(N(v)-v)+1=1$ (the first summand corresponds to complete subgraphs not containing $v$, the second to complete subgraphs containing $v$ and something else, the third to $\{v\}$.) $G$ is not a counterexample, contradiction.