*Maths week 10 graded assignment Complete Solutions Are Discussed In This Blog We Hope This Might Help You All In Matching Answers . Or For Some Others Reasons Not Able To Complete Graded Assignments *

1.The maximum number of non-zero entries in an adjacency matrix of a simple graph having $n$ vertices can be

*1 point*

2.We have a graph $G$ with 6 vertices. We write down the degrees of all vertices in $G$ in descending order. Which of the following is a possible listing of the degrees?

*1 point*

Stack

*1 point*

4.Suppose we obtain the following BFS tree rooted at node 1 for an undirected graph with vertices $(1,2,3,4,5,…..14).$

Which of the following cannot be an edge in the original graph?

2 MUTIPLE SELECT QUESTIONS:

*1 point*

Which of the following graphs satisfies the below properties:

1. $∣VC(G)∣$ = $3$, where $VC(G)$ is the minimum vertex cover of a graph $G.$

2. $∣PM(G)∣$ = $3$, where $PM(G)$ is the perfect matching of a graph $G.$

3. The graph is a 3-colouring.

**CORRECT Answers c And D**

*1 point*

3 NUMERICAL ANSWER TYPE:

If A = $⎣⎡0101000101101001000001100111000100001010000001000⎦⎤$ represents adjacency matrix of a graph $G,$ then the cardinality of the maximum independent set of the graph $G$ is

*1 point*

A company manufactures $10$ chemicals $x_{1},x_{2},x_{3},….x_{10}.$ Certain pairs of these chemicals are incompatible and would cause explosions if brought into contact with each other. Below graph shows the incompatibility of the chemicals, each vertex represents the chemical and each edge between a pair of chemicals represents that those two chemicals are incompatible. As a precautionary measure the company wishes to partition its warehouse into compartments, and store incompatible chemicals in different compartments. What is the least number of compartments into which the warehouse should be partitioned?

**3**

*1 point*

10. An incomplete undirected graph is given below and the numbering on each vertex denotes the colouring of the graph(‘$1$‘ denotes color 1, ‘$2$’ denotes color $2$, and ‘$3$’ denotes color $3$). Find the number of maximum edges that can be added to the given graph such that the colouring is retained and the graph is planar.

NOTE: Planar graph is a graph that can be drawn on the plane in such a way that its edges intersect only at their endpoints.

**6**