PLEASE HELP Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an u...

Question

Question

PLEASE HELP Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an u...

PLEASE HELP

Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an unordered pair (u, v), such that dist(u, v) = 2. Prove that G has at least n(n − 1) amicable pairs of vertices.

math geometry

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

Suppose v1,v2,v3.....vn are the n-vertices of graph.

We also know that maximum number of degree of any vertex is n-1.

d(v1)=(n-1)

d(v2)=(n-1)

...... d(vn)=(n-1)

Now , i- 1 i- 1 We know thot of odd degmnees even Sum ol degree o a yertices in a qor aph G is cven eoual to e 1

Considered unordered pair(u,v) with dist(u,v)=2.

G has atleast n(n-1) amicable pair of vertices .

Complete graph is taken.

Add a comment

Answer 2

Similar Homework Help Questions

49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then...

49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is connected. b. Show that the result in (a) is best possible; that is, for each n 2 2, prove there is a graph with ("2) edges that is not connected. 49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is...
Let G be a simple graph with 2n, n 2 vertices. Suppose there are at least n2 1 edges. Show that at least one triangle i...

Let G be a simple graph with 2n, n 2 vertices. Suppose there are at least n2 1 edges. Show that at least one triangle is formed. Hint: Check n 2 first and then use induction Let G be a simple graph with 2n, n 2 vertices. Suppose there are at least n2 1 edges. Show that at least one triangle is formed. Hint: Check n 2 first and then use induction
Let G be a graph with n vertices and n edges. (a) Show that G has...

Let G be a graph with n vertices and n edges. (a) Show that G has a cycle. (b) Use part (a) to prove that if G has n vertices, k components, and n − k + 1 edges, then G has a cycle.

Most Edges. Prove that if a graph with n vertices has chromatic number n, then the...

Most Edges. Prove that if a graph with n vertices has chromatic number n, then the graph has n(n-1) edges. Divide. Let V = {1, 2, ..., 10} and E = {(x, y) : x, y € V, x + y, , and a divides y}. Draw the directed graph with vertices V and directed edges E.
Let G be a directed graph on n vertices and maximum possible directed edges; assume that...

Let G be a directed graph on n vertices and maximum possible directed edges; assume that n ≥ 2. (a) How many directed edges are in G? Present such a digraph when n = 3 assuming vertices are 1, 2, and 3. You do not have to present a diagram, if you do not want to; you can simply present the directed edges as a set of ordered pairs. b) Is G, as specified in the problem, reflexive? Justify briefly....
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph...

Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v that is an element of S provided that {u,v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of G, that is...

Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u)...

Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u) +8()2 k, for some k> O. Show that G contains a path of length k. Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u) +8()2 k, for some k> O. Show that G contains a path of length k.
Let G be a graph with n vertices. Show that if the sum of degrees of...

Let G be a graph with n vertices. Show that if the sum of degrees of every pair of vertices in G is at least n − 1 then G is connected.
Let G be a connected graph with n vertices and n edges. How many cycles does...

Let G be a connected graph with n vertices and n edges. How many cycles does G have? Explain your answer.

Bounds on the number of edges in a graph. (a) Let G be an undirected graph...

Bounds on the number of edges in a graph. (a) Let G be an undirected graph with n vertices. Let Δ(G) be the maximum degree of any vertex in G, δ(G) be the minimum degree of any vertex in G, and m be the number of edges in G. Prove that δ(G)n2≤m≤Δ(G)n2

PLEASE HELP Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an u...

Homework Answers

Add Answer to:
PLEASE HELP Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an u...

Post as a guest

Earn Coins

49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then...

Let G be a simple graph with 2n, n 2 vertices. Suppose there are at least n2 1 edges. Show that at least one triangle i...

Let G be a graph with n vertices and n edges. (a) Show that G has...

Most Edges. Prove that if a graph with n vertices has chromatic number n, then the...

Let G be a directed graph on n vertices and maximum possible directed edges; assume that...

Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph...

Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u)...

Let G be a graph with n vertices. Show that if the sum of degrees of...

Let G be a connected graph with n vertices and n edges. How many cycles does...

Bounds on the number of edges in a graph. (a) Let G be an undirected graph...

PLEASE HELP Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an u...

Homework Answers

Add Answer to: PLEASE HELP Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an u...

Post as a guest

Earn Coins

Add Answer to:
PLEASE HELP Let G is a graph with 2n vertices and n^2 edges. An amicable pair of vertices is an u...