Problem
Assume that we have constructed a clique tree T for a given Bayesian network graph G, and that each of the cliques in T contains at most k nodes. Now, the user decides to add a single edge to the Bayesian network, resulting in a network G'. (The edge can be added between any pair of nodes in the network, so long as it maintains acyclicity.) What is the tightest bound you can provide on the maximum clique size in a clique tree T' for G'? Justify your response by explaining how to construct such a clique tree.