11.2.2023
Question 1: Consider the following graph $G=(V, E)$ with $\vert V \vert = 10$ and $\vert E \vert = 12$.
Which of the following is not an induced subgraph?
(3 points)
A. $\{\{a,d\}\,\{d,j\},\{g,j\},\{a,g\}\}$
B. $\{\{a,d\},\{d,j\},\{g,j\},\{a,g\},\{g,e\}\}$
C. $\{\{a,d\},\{d,j\},\{g,j\},\{a,g\},\{g,e\},\{e,f\}\}$
D. None, all are induced subgraphs.
Answer
D. None, all are induced subgraphs.Question 2: Consider the following graph $G=(V, E)$ with $\vert V \vert = 10$ and $\vert E \vert = 12$.
If you removed vertex b (and its incident edges) from $G$, how many spanning subgraphs of the original graph $G$ could you produce?
(3 points)
A. 0
B. 1
C. 2
D. 10
Answer
A. 0Question 3: Consider the following graph $G=(V, E)$ with $\vert V \vert = 10$ and $\vert E \vert = 12$.
Suppose the subgraph $G’$ is obtained by from $G$ by removing vertices h and e (and all their incident edges). What is $K(G’)$?
(3 points)
A. 1
B. 2
C. 3
D. 8