(a) Explanation Given information: Suppose that G is a graph with adjacency matrix A. Proof: As noted in the text, the number of ( i , j ) entry lengths in A 2 denotes j from 2 to I . This is because the square of matrix A is the dot product of its rows in order of matrix multiplication. So, in the dot product of i t h row with j t h column, only those terms contribute which have 1 at the same position (b) To determine To prove: Let d i denote the degree of the vertex v i in G . Show that the sum of the entries of A 2 is also ∑ d 1 2

Discrete Mathematics with Graph Theory (Classic Version) (3rd Edition) (Pearson Modern Classics for Advanced Mathematics Series)

3rd Edition

ISBN: 9780134689555

Author: Edgar Goodaire, Michael Parmenter

Publisher: PEARSON

See similar textbooks

Videos

Question

Chapter 10.3, Problem 6E

(a)

To determine

To Prove: The number of walks of length 2 in G is the sum of the entries of the matrix A2.

(b)

To determine

To prove: Let di denote the degree of the vertex vi in G. Show that the sum of the entries of A2 is also ∑d12

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 10.3, Problem 5E

Chapter 10.3, Problem 7E

Students have asked these similar questions

use Cauchy Mean-Value Theorem to derive Corollary 12.6.2, and then derive 12.6.3

Explain the focus and reasons for establishment of 12.5.4

explain how to 12.3.1 from 11.3.6

Chapter 10 Solutions

Discrete Mathematics with Graph Theory (Classic Version) (3rd Edition) (Pearson Modern Classics for Advanced Mathematics Series)

Ch. 10.1 - Prob. 1TFQ Ch. 10.1 - A path is a walk in which all vertices are...Ch. 10.1 - 3. A trail is a path Ch. 10.1 - A path is trail.Ch. 10.1 - A cycle is a special type of circuit.Ch. 10.1 - 6. A cycle is a circuit with no repeated edges Ch. 10.1 - 7. An Eulerian circuit is a cycle. Ch. 10.1 - Prob. 8TFQ Ch. 10.1 - A sub graph of a connected graph must be...Ch. 10.1 - Prob. 10TFQ

Ch. 10.1 - K8,10 is Eulerian.Ch. 10.1 - Prob. 12TFQ Ch. 10.1 - 13. A graph with more than one component cannot be...Ch. 10.1 - Prob. 1E Ch. 10.1 - [BB] Answer the Konigsberg bridge Problem and...Ch. 10.1 - Prob. 3E Ch. 10.1 - Prob. 4E Ch. 10.1 - Prob. 5E Ch. 10.1 - 6. Suppose we modify the definition of Eulerian...Ch. 10.1 - 7. (a) Is there an Eulerian trail from A to B in...Ch. 10.1 - [BB] (Fictitious) A recently discovered map of the...Ch. 10.1 - 9. Euler’s original article about the Konigsberg...Ch. 10.1 - Prob. 10E Ch. 10.1 - Prob. 11E Ch. 10.1 - [BB] For which values of n1 , if any, is Kn...Ch. 10.1 - 13. (a) Find a necessary and sufficient condition...Ch. 10.1 - Prob. 14E Ch. 10.1 - 15.[BB] Prove that any circuit in the graph must...Ch. 10.1 - Prob. 16E Ch. 10.1 - Prob. 17E Ch. 10.1 - Prob. 18E Ch. 10.1 - Prob. 19E Ch. 10.1 - Prob. 20E Ch. 10.1 - Prob. 21E Ch. 10.1 - Prob. 22E Ch. 10.1 - Prob. 23E Ch. 10.1 - Prob. 24E Ch. 10.1 - 25. Prove that a graph is bipartite if and only if...Ch. 10.1 - Prob. 26E Ch. 10.1 - Prob. 27E Ch. 10.2 - A Hamiltonian cycle is a circuit. Ch. 10.2 - Prob. 2TFQ Ch. 10.2 - Prob. 3TFQ Ch. 10.2 - Prob. 4TFQ Ch. 10.2 - Prob. 5TFQ Ch. 10.2 - A graph that contains a proper cycle cannot be...Ch. 10.2 - Prob. 7TFQ Ch. 10.2 - Prob. 8TFQ Ch. 10.2 - Prob. 9TFQ Ch. 10.2 - Prob. 10TFQ Ch. 10.2 - Prob. 1E Ch. 10.2 - 2. Determine whether or not each of the graphs of...Ch. 10.2 - Determine whether each of the graph shown is...Ch. 10.2 - Prob. 4E Ch. 10.2 - Consider the graph shown. Is it Hamiltonian? Is...Ch. 10.2 - Prob. 6E Ch. 10.2 - Prob. 7E Ch. 10.2 - Does the graph have a Hamiltonian cycle that...Ch. 10.2 - Prob. 9E Ch. 10.2 - Prob. 10E Ch. 10.2 - How many edges must a Hamiltonian cycle is kn...Ch. 10.2 - 12. Draw a picture of a cube, by imagining that...Ch. 10.2 - Prob. 13E Ch. 10.2 - Prob. 14E Ch. 10.2 - Prob. 15E Ch. 10.2 - Prob. 16E Ch. 10.2 - Suppose G is a graph with n3 vertices and at least...Ch. 10.2 - 18.[BB] Suppose G is a graph with vertices such...Ch. 10.2 - Prob. 19E Ch. 10.2 - Prob. 20E Ch. 10.2 - Answer true of false and in each case either given...Ch. 10.2 - Prob. 22E Ch. 10.2 - Prob. 23E Ch. 10.2 - Find a necessary and sufficient condition on m and...Ch. 10.3 - Prob. 1TFQ Ch. 10.3 - Prob. 2TFQ Ch. 10.3 - Prob. 3TFQ Ch. 10.3 - Prob. 4TFQ Ch. 10.3 - Prob. 5TFQ Ch. 10.3 - Prob. 6TFQ Ch. 10.3 - Prob. 7TFQ Ch. 10.3 - Prob. 8TFQ Ch. 10.3 - Prob. 9TFQ Ch. 10.3 - Prob. 10TFQ Ch. 10.3 - Prob. 1E Ch. 10.3 - Prob. 2E Ch. 10.3 - Prob. 3E Ch. 10.3 - Prob. 4E Ch. 10.3 - Prob. 5E Ch. 10.3 - Prob. 6E Ch. 10.3 - Prob. 7E Ch. 10.3 - 8. (a) [BB] Find the adjacency matrices and of...Ch. 10.3 - 9. Repeat Exercise 8 for the graphs and shown....Ch. 10.3 - Prob. 10E Ch. 10.3 - Let A=[abcpqrxyz] and let P=[010001100]. Thus P is...Ch. 10.3 - Prob. 12E Ch. 10.3 - 13. For each pair of matrices shown, decide...Ch. 10.3 - 14. [BB] Let A be the adjacency matrix of a...Ch. 10.3 - Prob. 15E Ch. 10.3 - Prob. 16E Ch. 10.3 - Prob. 17E Ch. 10.3 - Prob. 18E Ch. 10.4 - Prob. 1TFQ Ch. 10.4 - Prob. 2TFQ Ch. 10.4 - It is an open question as to whether there exists...Ch. 10.4 - Prob. 4TFQ Ch. 10.4 - Prob. 5TFQ Ch. 10.4 - Prob. 6TFQ Ch. 10.4 - Prob. 7TFQ Ch. 10.4 - Prob. 8TFQ Ch. 10.4 - Prob. 9TFQ Ch. 10.4 - Prob. 10TFQ Ch. 10.4 - Prob. 1E Ch. 10.4 - Prob. 2E Ch. 10.4 - Prob. 3E Ch. 10.4 - Prob. 4E Ch. 10.4 - Prob. 5E Ch. 10.4 - Prob. 6E Ch. 10.4 - Prob. 7E Ch. 10.4 - Prob. 8E Ch. 10.4 - Prob. 9E Ch. 10.4 - Prob. 10E Ch. 10.4 - Prob. 11E Ch. 10.4 - 12. [BB] Could Dijkstra’s algorithm (original...Ch. 10.4 - Prob. 13E Ch. 10.4 - 14. (a) If weights were assigned to the edges of...Ch. 10.4 - Prob. 15E Ch. 10.4 - Prob. 16E Ch. 10.4 - Prob. 17E Ch. 10.4 - Prob. 18E Ch. 10.4 - Prob. 19E Ch. 10.4 - Prob. 20E Ch. 10.4 - Prob. 21E Ch. 10.4 - Prob. 22E Ch. 10.4 - Prob. 23E Ch. 10.4 - Prob. 24E Ch. 10 - In the Konigsberg Bringe Problem (see fig. 9.1),...Ch. 10 - Prob. 2RE Ch. 10 - Suppose G1 and G2 are graphs with no vertices in...Ch. 10 - Prob. 4RE Ch. 10 - Prob. 5RE Ch. 10 - Is the graph Hamiltonian? Is it Eulerian? Explain...Ch. 10 - Determine, with reason, whether each of the...Ch. 10 - Prob. 8RE Ch. 10 - Prob. 9RE Ch. 10 - Prob. 10RE Ch. 10 - Prob. 11RE Ch. 10 - Prob. 12RE Ch. 10 - Prob. 13RE Ch. 10 - Prob. 14RE Ch. 10 - 15. A connected graph G has 10 vertices and 41...Ch. 10 - Prob. 16RE Ch. 10 - Let v1,v2,........v8 and w1,w2,..........w12 be...Ch. 10 - Prob. 18RE Ch. 10 - Martha claims that a graph with adjacency...Ch. 10 - Prob. 20RE Ch. 10 - Which of the following three matrices (if any) is...Ch. 10 - Apply the first form of Dijkstras algorithm to the...Ch. 10 - Prob. 23RE Ch. 10 - 24. Apply the original form of Dijkstra’s...Ch. 10 - Apply the improved version of Dijkstras algorithm...Ch. 10 - Prob. 26RE Ch. 10 - 27. Apply the Floyd- Warshall algorithm apply to...Ch. 10 - Prob. 28RE

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

To Prove: The number of walks of length 2 in G is the sum of the entries of the matrix A 2 .

Solution Summary: The author explains how to prove that the number of walks of length 2 in G is the sum of entries of the matrix A2.

Videos

To Prove: The number of walks of length 2 in G is the sum of the entries of the matrix A2.

To prove: Let di denote the degree of the vertex vi in G. Show that the sum of the entries of A2 is also ∑d12

Want to see the full answer?

Chapter 10 Solutions