Homework: Answer questions regarding Matrix properties of graphs and Trees Q1) a
ID: 3283359 • Letter: H
Question
Homework:
Answer questions regarding Matrix properties of graphs and Trees
Q1)
a) True or False: The adjacency matrix for any graph with 5 edges has 5 rows and 5 columns.
b) True or False: The adjacency matrix of any graph with n vertices has the property that the entry in row i and column j equals the entry in row j and column i for any positive integers i and j that are less than or equal to n.
c)True or False: In the incidence matrix of any graph the number of rows is equal to the number of columns.
d)True or False: The sum of the entries in the incidence matrix of any graph is equal to twice the number of edges in the graph.
e)
Which of the following is true?
Every simple graph with 5 vertices and 4 edges is a tree.
Every connected graph with 8 vertices and 9 edges is a tree.
Every simple connected graph with 6 vertices and 7 edges is a tree.
d. Every tree with 11 vertices is simple, connected and has 10 edges.
f)
True or False: If any edge is removed from a tree, then the resulting graph is not connected
a.Every simple graph with 5 vertices and 4 edges is a tree.
b.Every connected graph with 8 vertices and 9 edges is a tree.
c.Every simple connected graph with 6 vertices and 7 edges is a tree.
d. Every tree with 11 vertices is simple, connected and has 10 edges.
f)
True or False: If any edge is removed from a tree, then the resulting graph is not connected
Explanation / Answer
a) false. Number of rows an columns are number of vertices.
b) True. both are the number of edges between two vertices
c)False
If there are ‘n’ number of rows in a given incidence matrix, that means in a graph there are ‘n’ number of nodes. Similarly, if there are ‘m’ number of columns in that given incidence matrix, that means in that graph there are ‘m’ number of branches. So m and n need not be equal.
d) True
The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.