search
Log In

Recent questions tagged graph-theory

0 votes
1 answer
1
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ if and only if either $j=i+1$ or $j=3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is ______ $23$ $99$ $4$ $7$
asked Nov 20, 2020 in Discrete Mathematics jothee 77 views
0 votes
1 answer
2
Consider the following statements: Any tree is $2$-colorable A graph $G$ has no cycles of even length if it is bipartite A graph $G$ is $2$-colorable if is bipartite A graph $G$ can be colored with $d+1$ colors if $d$ is the maximum degree of any vertex in the graph $G$ ... and $(e)$ are incorrect $(b)$ and $(c)$ are incorrect $(b)$ and $(e)$ are incorrect $(a)$ and $(d)$ are incorrect
asked Nov 20, 2020 in Discrete Mathematics jothee 35 views
0 votes
0 answers
3
Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$. Consider the following statements. Statement $I$: No edge of $G$ is a cross with respect to $T_D$ Statement $II$: For every edge $(u,v)$ of $G$ ... Statement $I$ and Statement $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
asked Nov 20, 2020 in Discrete Mathematics jothee 33 views
3 votes
3 answers
6
1 vote
1 answer
7
0 votes
2 answers
8
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is $13$ $14$ $12$ $11$
asked Mar 31, 2020 in Graph Theory Lakshman Patel RJIT 395 views
1 vote
1 answer
10
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to: $3$ $4$ $5$ $6$
asked Mar 31, 2020 in Graph Theory Lakshman Patel RJIT 204 views
0 votes
1 answer
11
0 votes
2 answers
12
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list representation is easier than ... matrix representation. Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 1.4k views
0 votes
1 answer
13
0 votes
1 answer
14
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 204 views
0 votes
1 answer
15
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 154 views
0 votes
1 answer
16
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 216 views
0 votes
1 answer
17
0 votes
1 answer
18
0 votes
1 answer
19
0 votes
1 answer
20
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 322 views
0 votes
4 answers
21
0 votes
3 answers
22
0 votes
7 answers
23
0 votes
4 answers
24
0 votes
2 answers
25
Choose the most appropriate definition of plane graph. A simple graph which is isomorphic to hamiltonian graph. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset $X$ and $Y$ in such a way that each edge ... . A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices. None of the option.
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 546 views
0 votes
1 answer
26
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to: $15$ $30$ $56$ $60$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 567 views
1 vote
4 answers
27
0 votes
1 answer
28
Consider a Hamiltonian Graph $G$ with no loops or parallel edges and with $\left | V\left ( G \right ) \right |= n\geq 3$. The which of the following is true? $\text{deg}\left ( v \right )\geq \frac{n}{2}$ for each vertex $v\\$ ... $v$ and $w$ are not connected by an edge All of the above
asked Mar 24, 2020 in Graph Theory jothee 214 views
6 votes
3 answers
29
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______
asked Feb 12, 2020 in Graph Theory Arjun 3.2k views
...