Graph entropy
In information theory, the graph entropy is a measure of the information rate achievable by communicating symbols over a channel in which certain pairs of values may be confused. This measure, first introduced by Körner in the 1970s, has since also proven itself useful in other settings, including combinatorics. Definition. Let formula_1 be an undirected graph. The graph entropy of formula_2, denoted formula_3 is defined as where formula_5 is chosen uniformly from formula_6, formula_7 ranges over independent sets of G, the joint distribution of formula_5 and formula_7 is such that formula_10 with probability one, and formula_11 is the  mutual information of formula_5 and formula_7. That is, if we let formula_14 denote the independent vertex sets in formula_2, we wish to find the joint distribution formula_16 on formula_17 with the lowest mutual information such that (i) the marginal distribution of the first term is uniform and (ii) in samples from the distribution, the second term contains the first term almost surely. The mutual information of formula_5 and formula_7 is then called the entropy of formula_2. Properties. Additionally, simple formulas exist for certain families classes of graphs. Example. Here, we use properties of graph entropy to provide a simple proof  that a complete graph formula_2 on formula_32 vertices cannot be expressed as the union of fewer than formula_33 bipartite graphs. "Proof" By monotonicity, no bipartite graph can have graph entropy greater than that of a complete bipartite graph, which is bounded by formula_35. Thus, by sub-additivity, the union of formula_44 bipartite graphs cannot have entropy greater than formula_44. Now let formula_1 be a complete graph on formula_32 vertices. By the properties listed above, formula_48. Therefore, the union of fewer than formula_33 bipartite graphs cannot have the same entropy as formula_2, so formula_2 cannot be expressed  as such a union. formula_52