search
Log In

Recent questions tagged graph-theory

1 vote
2 answers
1
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
asked Feb 18 in Graph Theory Arjun 506 views
3 votes
2 answers
2
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
asked Feb 18 in Graph Theory Arjun 584 views
0 votes
1 answer
3
In an undirected graph, if we add the degrees of all vertices, it is: odd even cannot be determined always $n+1,$ where $n$ is number of nodes
asked Dec 9, 2020 in Unknown Category gatecse 32 views
0 votes
1 answer
4
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 175 views
0 votes
1 answer
5
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 221 views
0 votes
0 answers
6
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 92 views
3 votes
3 answers
9
1 vote
1 answer
10
0 votes
2 answers
11
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 544 views
1 vote
1 answer
13
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 281 views
0 votes
1 answer
14
0 votes
2 answers
15
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 3.1k views
0 votes
1 answer
16
0 votes
1 answer
17
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 246 views
0 votes
1 answer
18
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 183 views
0 votes
1 answer
19
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 324 views
0 votes
1 answer
20
0 votes
1 answer
21
0 votes
1 answer
22
0 votes
1 answer
23
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 508 views
0 votes
4 answers
24
0 votes
3 answers
25
0 votes
7 answers
26
...