Question

In: Advanced Math

2. Let G be a bipartite graph with 10^7 left vertices and 20 right vertices. Two...

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.

Expert Solution

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.

Colby Messinger answered 2 years ago

Let G be a bipartite graph with 107 left vertices and 20 right vertices. Two vertices...

Let G be a bipartite graph with 107 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. Bonus: Show that G has triplets. What about quadruplets, etc.?

1) a) Let k ≥ 2 and let G be a k-regular bipartite graph. Prove that G...

1) a) Let k ≥ 2 and let G be a k-regular bipartite graph. Prove that G has no cut-edge. (Hint: Use the bipartite version of handshaking.) b) Construct a simple, connected, nonbipartite 3-regular graph with a cut-edge. (This shows that the condition “bipartite” really is necessary in (a).) 2) Let F_n be a fan graph and Let a_n = τ(F_n) where τ(F_n) is the number of spanning trees in F_n. Use deletion/contraction to prove that a_n = 3a_n-1 - a_n-2...

Problem 8. A bipartite graph G = (V,E) is a graph whose vertices can be partitioned...

Problem 8. A bipartite graph G = (V,E) is a graph whose vertices can be partitioned into two (disjoint) sets V1 and V2, such that every edge joins a vertex in V1 with a vertex in V2. This means no edges are within V1 or V2 (or symbolically: ∀u, v ∈ V1, {u,v} ∉ E and ∀u,v ∈ V2, {u,v} ∉ E). 8(a) Show that the complete graph K2 is a bipartite graph. 8(b) Prove that no complete graph Kn,...

9. Let G be a bipartite graph and r ∈ Z>0. Prove that if G is...

9. Let G be a bipartite graph and r ∈ Z>0. Prove that if G is r-regular, then G has a perfect matching.1 10. Let G be a simple graph. Prove that the connection relation in G is an equivalence relation on V (G)

Let G be a bipartite graph and r ∈ Z>0. Prove that if G is r-regular,...

Let G be a bipartite graph and r ∈ Z>0. Prove that if G is r-regular, then G has a perfect matching. HINT: Use the Marriage Theorem and the Pigeonhole Principle. Recall that G is r-regular means every vertex of G has degree

A bipartite graph is drawn on a channel if the vertices of one partite set are...

A bipartite graph is drawn on a channel if the vertices of one partite set are placed on one line in the plane (in some order) and the vertices of the other partite set are placed on a line parallel to it and the edges are drawn as straight-line segments between them. Prove that a connected graph G can be drawn on a channel without edge crossings if and only if G is a caterpillar. (***Please do on paper)

Let G be a graph whose vertices are the integers 1 through 8, and let the...

Let G be a graph whose vertices are the integers 1 through 8, and let the adjacent vertices of each vertex be given by the table below: vertex adjacent vertices 1 (2, 3, 4) 2 (1, 3, 4) 3 (1, 2, 4) 4 (1, 2, 3, 6) 5 (6, 7, 8) 6 (4, 5, 7) 7 (5, 6, 8) 8 (5, 7) Assume that, in a traversal of G, the adjacent vertices of a given vertex are returned in the...

Question 2: A bipartite graph with 2n vertices (namely |V1| = |V2| = n) is d-regular...

Question 2: A bipartite graph with 2n vertices (namely |V1| = |V2| = n) is d-regular if and only if the degree of every vertex in V1 ∪ V2 is exactly d. Show that a d-regular bipartite graph always has a perfect matching (a matching of size n that includes all vertices). ***Remarks: All the graphs here are without self loops and parallel or anti-parallel edges. A network is a directed graph with source s and sink t and capacity...

Let Q:= {1,2,...,q}. Let G be a graph with the elements of Q^n as vertices and...

Let Q:= {1,2,...,q}. Let G be a graph with the elements of Q^n as vertices and an edge between (a1,a2,...,an) and (b1,b2,...bn) if and only if ai is not equal to bi for exactly one value of i. Show that G is Hamiltonian.

let G be a simple graph. show that the relation R on the set of vertices...

let G be a simple graph. show that the relation R on the set of vertices of G such that URV if and only if there is an edge associated with (u,v) is a symmetric irreflexive relation on G