Graph entropy: Difference between revisions

Revision as of 18:10, 21 October 2019

Revision as of 18:11, 21 October 2019

Line 24:

Here, we use properties of graph entropy to provide a simple proof that a complete graph <math>G</math> on <math>n</math> vertices cannot be expressed as the union of fewer than <math>\lg n</math> bipartite graphs.

''Proof'' By monotonicity, no bipartite graph can have graph entropy greater than that of a complete bipartite graph, which is bounded by <math>1</math>. Thus, by sub-additivity, the union of <math>k</math> bipartite graphs cannot have entropy greater than <math>k</math>. Now let <math>G = (V, E)</math> be a complete graph on <math>n</math> vertices. By the properties listed above, <math>H(G) = \lglog_2 n</math>. Therefore, the union of fewer than <math>\lglog_2 n</math> bipartite graphs cannot have the same entropy as <math>G</math>, so <math>G</math> cannot be expressed as such a union. <math>\blacksquare</math>

==General References==