In: Advanced Math
2. Let G be a bipartite graph with 10^7 left vertices and 20 right vertices. Two vertices u, v are called twins if the set of neighbors of u equals the set of neighbors of v (triplets, quadruplets etc are defined similarly). Show that G has twins. Show that G has triplets. What about quadruplets, etc.?
3. Show that there exists a bipartite graph with 10^5 left vertices and 20 right vertices without any twins.
4. Show that any graph with n vertices and δ(G) ≥ n/2 + 1 has a triangle.
2. First part:
The set of neighbours of a left vertex is a subset of the set
of the right vertices. Since there are
of right vertices,
there are
subsets of right vertices. Thus, the set of neighbours of a left
vertex must be one of these
subsets of right vertices. Now suppose that there are no
twins; we will derive contradiction. The set of neighbours
of every left vertex is different from that of any other left
vertex. That is, there must be at least
set of neighbours,
which means at least
subsets of right
vertices. Thus, we must have
. Taking logarithm, this means
which is absurd. Hence, must have
twins.
Second part:
Now suppose that there are no triples; we will derive
contradiction. Every subset of right vertices can be the
set of neighbours of at most two left vertices. Let be the set of right
vertices and
be the set of left
vertices. Let
be power set of
, and
be the function given as follows:
This function is such that means
. Then, above means
for all
. But
this means there are at most
left vertices, so that
. Taking logarithm, this means
which is absurd. Hence, must have
triples.
Third part:
For quadruples, the above arguments (which are essentially pigeon-hole principle) do not apply.
3. Let
and
. There are
nonempty
subsets of
. Let us call them
. Note that
(by calculator). Hence, the function
, given by
is
well-defined. Now consider the bipartite graph
where
if and only if
. This
is a bipartite graph, and it has no twin because the neighbour
function
is injective.