TransWikia.com

A complete bipartite graph is unique

Mathematics Asked by ItsNotMe on December 15, 2020

Let G be a complete bipartite graph with bipartition {X, Z} in independent sets. Prove that G is unique.

I have the idea about the statement but I have some trouble proving it.
A complete bipartite graph means that every $x in X$ is connected to every $z in Z$, but I don’t know how to work with that hipotesis…

One Answer

You know that each node $x in X$ is connected to each $z in Z$. If you were to assume that there are two bipartite graphs that do not have the same edge set, you can create a contradiction, since both graphs are complete and thus they must have the same edge set.

You could compare both and if an edge is in both edge sets, remove it. You will end up with two empty sets (if an edge is not in one of the sets, the graphs is not complete) and thus have proven that they are equal since it contradicts the assumption that there must be at least one edge in one of the two graphs that is not in the other.

Correct answer by teun on December 15, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP