search
Log In

Recent questions tagged graph-theory

1 vote
1 answer
4
0 votes
2 answers
5
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 in Graph Theory Lakshman Patel RJIT 157 views
1 vote
1 answer
7
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 in Graph Theory Lakshman Patel RJIT 111 views
0 votes
2 answers
9
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 in Graph Theory Lakshman Patel RJIT 193 views
0 votes
1 answer
10
0 votes
1 answer
11
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 in Graph Theory Lakshman Patel RJIT 121 views
0 votes
1 answer
12
0 votes
1 answer
13
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 in Graph Theory Lakshman Patel RJIT 106 views
0 votes
1 answer
14
0 votes
1 answer
15
0 votes
1 answer
17
0 votes
3 answers
19
0 votes
7 answers
20
0 votes
2 answers
22
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 in Graph Theory Lakshman Patel RJIT 254 views
0 votes
1 answer
23
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 in Graph Theory Lakshman Patel RJIT 274 views
1 vote
4 answers
24
0 votes
1 answer
25
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 in Graph Theory jothee 158 views
6 votes
3 answers
26
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 in Graph Theory Arjun 2.3k views
0 votes
3 answers
27
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$
asked Feb 11 in Graph Theory Lakshman Patel RJIT 241 views
2 votes
1 answer
28
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match requires a ... to solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
asked Sep 13, 2019 in Graph Theory gatecse 190 views
5 votes
2 answers
29
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$
asked Sep 13, 2019 in Graph Theory gatecse 179 views
1 vote
1 answer
30
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each ... is: Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
asked Sep 13, 2019 in Graph Theory gatecse 132 views
...