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!

Related Questions

How to compute $sum_{n=1}^infty{frac{n}{(2n+1)!}}$?

3  Asked on September 18, 2020 by samuel-a-morales


Rational Roots (with Lots of Square Roots!)

1  Asked on September 16, 2020 by fleccerd


Is a relation that is purely reflexive also symmetric?

1  Asked on September 13, 2020 by paul-j


$3^{123} mod 100$

4  Asked on September 13, 2020 by global05


Totally order turing machines by halting

1  Asked on September 10, 2020 by donald-hobson


Density of Tensor Products

0  Asked on September 8, 2020 by jacob-denson


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP