Content deleted Content added
Line 22:
==Example==
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>\
''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) = \log_2 n</math>. Therefore, the union of fewer than <math>\log_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>
| |||