Register

GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 11

• edited by
394 views
1 1 vote

For which of the following does there exist a simple undirected graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ satisfying the specified conditions?

  1. $\text{G}$ has $3$ components, $20$ vertices and $16$ edges.
  2. $\text{G}$ has $12$ vertices, $28$ edges and the degree of each vertex is either $3$ or $6.$

 

  1. Only I
  2. Only II
  3. Both
  4. None

1 Answer

1 1 vote

 

  1. Let $\mathrm{G}$ be a simple graph of order(vertices) $n$ and $k$ components. Then the size(edges) of $\mathrm{G}$ is at least $n-k$.
  2.  

​​​​​​​

 

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes Test Seri...Next → · GO Classes Test Seri...
← Previous in category · GO Classes Test Seri...Next in category → · ISI2022 - MCS - PCB ...
Position:
Show:

Related questions

0 0 votes
1 1 answer
256
256 views
GO Classes asked Oct 16, 2024
256 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 14
A way to transform one undirected simple graph into another is by obtaining its subdivision. Intuitively, the subdivision of an undirected graph $\mathrm{G},$ denoted $\t...
0 0 votes
2 2 answers
258
258 views
GO Classes asked Oct 16, 2024
258 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 6
Which of the following is/are TRUE ?If we perform DFS on an undirected graph, there are no cross edges.If the DFS tree has no back edges, then there are no cycles in the ...
1 1 vote
1 1 answer
335
335 views
GO Classes asked Oct 16, 2024
335 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 7
Which of the following is correct option about $\mathrm{S} 1$ and $\mathrm{S} 2?$$\mathrm{S} 1:$ If $\text{G}$ is a weighted graph with $n$ vertices and $m$ edges that do...
0 0 votes
1 1 answer
240
240 views
GO Classes asked Oct 16, 2024
240 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 8
Consider the following directed, weighted graph:Even though the graph has negative weight edges, we use Dijkstra’s algorithm to calculate supposedly shortest paths from A...