Register

Recent questions tagged graph-connectivity

3 votes
1 answer
69
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 20
Which of the following graphs has a Hamiltonian path? $S_1:$ $S_2:$ $S_1$ only $S_2$ only Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$
Which of the following graphs has a Hamiltonian path?$S_1:$$S_2:$$S_1$ only$S_2$ onlyBoth $S_1$ and $S_2$Neither $S_1$ nor $S_2$
User Avatar
1 votes
2 answers
73
GATE Overflow Test Series | Mixed Subjects | Test 2 | Question: 7
If a simple graph $G,$ has $10$ vertices and $11$ edges, the number of edges in the complement of $G$ will be _______
If a simple graph $G,$ has $10$ vertices and $11$ edges, the number of edges in the complement of $G$ will be _______
User Avatar
3 votes
1 answer
74
GATE Overflow Test Series | Data Structures | Test 1 | Question: 1
The cut vertices in the given graph are E and F A, C and D C, E and F B and C
The cut vertices in the given graph areE and FA, C and DC, E and FB and C
User Avatar
0 votes
2 answers
75
CMI2019-B-4
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph....
User Avatar
1 votes
2 answers
77
CMI2018-B-3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
Let $G$ be a simple graph on $n$ vertices.Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.For every $n>2$, find a graph $G_{n}$ which has exa...
User Avatar
1 votes
1 answer
80
ISI2017-PCB-CS-1(b)
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
User Avatar
33 votes
14 answers
81
GATE CSE 2019 | Question: 12
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$
Let $G$ be an undirected complete graph on $n$ vertices, where $n 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to$n!$$(n-1)!$$1$$\frac{(n-1)!}{2}...
User Avatar
0 votes
1 answer
83
doubt
what is the diameter and radius of the complete bipartite graph?
what is the diameter and radius of the complete bipartite graph?
User Avatar
Page: