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.
Let G = ( V , E ) be an undirected graph. The graph entropy of G , denoted H ( G ) is defined as
where X is chosen uniformly from V , Y is an independent set in G, and I ( X ; Y ) is the mutual information of X and Y .
Monotonicity. If G 1 is a subgraph of G 2 on the same vertex set, then H ( G 1 ) ≤ H ( G 2 ) .Subadditivity. Given two graphs G 1 = ( V , E 1 ) and G 2 = ( V , E 2 ) on the same set of vertices, the graph union G 1 ∪ G 2 = ( V , E 1 ∪ E 2 ) satisfies H ( G 1 ∪ G 2 ) ≤ H ( G 1 ) + H ( G 2 ) .Arithmetic mean of disjoint unions. Let G 1 , G 2 , ⋯ , G k be a sequence of graphs on disjoint sets of vertices, with n 1 , n 2 , ⋯ , n k vertices, respectively. Then H ( G 1 ∪ G 2 ∪ ⋯ G k ) = 1 ∑ i = 1 k n i ∑ i = 1 k n i H ( G i ) .Additionally, simple formulas exist for certain families classes of graphs.
Edge-less graphs have entropy 0 .Complete graphs on n vertices have entropy lg n , where lg is the binary logarithm.Complete balanced k-partite graphs have entropy lg r where r is the binary logarithm. In particular, complete balanced bipartite graphs have entropy 1 .Complete bipartite graphs with n vertices in one partition and m in the other have entropy H ( n m + n ) , where H is the binary entropy function.Here, we use properties of graph entropy to provide a simple proof that a complete graph G on n vertices cannot be expressed as the union of fewer than lg n bipartite graphs.
Proof By monotonicity, no bipartite graph can have graph entropy greater than that of a complete bipartite graph, which is bounded by 1 . Thus, by sub-additivity, the union of k bipartite graphs cannot have entropy greater than k . Now let G = ( V , E ) be a complete graph on n vertices. By the properties listed above, H ( G ) = lg n . Therefore, the union of fewer than lg n bipartite graphs cannot have the same entropy as G , so G cannot be expressed as such a union. ◼
