Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Graph Theory:
Recent questions tagged graph-theory
2
votes
1
answer
601
graphs-eulerian
if a graph contains 2 components,1st component contains only one vertex and 2nd component is a cycle with 4 vertices. is this graph Eulerian? it should be Eulerian ryt?
if a graph contains 2 components,1st component contains only one vertex and 2nd component is a cycle with 4 vertices. is this graph Eulerian?it should be Eulerian ryt?
Anusha Motamarri
450
views
Anusha Motamarri
asked
Jan 6, 2017
Mathematical Logic
graph-theory
+
–
4
votes
0
answers
602
Relations and Combinatorics
$\begin{align*} &S = \left \{ G_i \;\; | \; G_i \in \text{ lebeled trees with 4 vertices} \right \} \\ &\text{Relation } \quad R = \left \{ {\color{red}{\left ( G_i,G_j \right )}} \; | G_i,G_j \in S \;\; \text{and} \;\; G_i,G_j \;\; \text{are} \;\; \text{isomorphic to each other} \right \} \end{align*}$ No of equivalent classes of $R$ ?
$\begin{align*} &S = \left \{ G_i \;\; | \; G_i \in \text{ lebeled trees with 4 vertices} \right \} \\ &\text{Relation } \quad R = \left \{ {\color{red}{\left ( G_i,G_j \...
dd
718
views
dd
asked
Jan 6, 2017
Combinatory
discrete-mathematics
combinatory
relations
graph-theory
+
–
2
votes
1
answer
603
graph theory
Assumed undirected graph G is connected. G has 6vertices and 10 edges. Find the minimum number of edges whose deletion from graph G is always guarantee that it will become disconnected.
Assumed undirected graph G is connected. G has 6vertices and 10 edges. Findthe minimum number of edges whose deletion from graph G is always guaranteethat ...
sanyam53
993
views
sanyam53
asked
Jan 3, 2017
Graph Theory
graph-theory
graph-connectivity
discrete-mathematics
+
–
2
votes
1
answer
604
MATCHING NUMBER
what is the matching number of $K_{2,3}$ graph.and also explain matching number of $K_{m,n}$(simplification).
what is the matching number of $K_{2,3}$ graph.and also explain matching number of $K_{m,n}$(simplification).
santhoshdevulapally
410
views
santhoshdevulapally
asked
Dec 31, 2016
Graph Theory
graph-theory
graph-matching
+
–
0
votes
0
answers
605
A graph $G$ is Eulerian path iff degree of each vertex is even with atmost one trivial component
For this proof ,proving $\Rightarrow$ If Graph $G$ is eulerian then degree of each vertex is even with atmost one trivial component. As $G$ is Eulerian ,it means it **must not** repeat Edges but can repeat ... $C,F =3$ contradictory.... help me out where i am wrong
For this proof ,proving$\Rightarrow$ If Graph $G$ is eulerian then degree of each vertex is even with atmost one trivial component.As $G$ is Eulerian ,it means it must n...
Anand.
573
views
Anand.
asked
Dec 31, 2016
Graph Theory
graph-theory
engineering-mathematics
+
–
1
votes
2
answers
606
CMI2016-B-3
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example: Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:Show that for every undirected graph, there is a way...
go_editor
779
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
descriptive
graph-theory
graph-connectivity
+
–
1
votes
1
answer
607
CMI2016-B-2b
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple cycle of length at least $k+1$.
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively ...
go_editor
471
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
graph-connectivity
descriptive
+
–
1
votes
2
answers
608
CMI2016-B-2a
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple path of length at least $k$.
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (resp...
go_editor
517
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
descriptive
graph-connectivity
+
–
1
votes
2
answers
609
CMI2016-A-9
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected-there is a path from each city to every other city. The contract requires the network to remain ... $34$ $32$ $17$ $16$
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is ...
go_editor
913
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
graph-connectivity
+
–
1
votes
2
answers
610
CMI2016-A-5
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices? $60$ edges and $20$ vertices $30$ edges and $20$ vertices $60$ edges and $50$ vertices $30$ edges and $50$ vertices
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices?$60$ edges and $20$ vertices$30$ ed...
go_editor
570
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
undirected-graph
regular-pentagon
+
–
0
votes
2
answers
611
CMI2016-A-4
Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has weight $53$ and the shortest path from $s$ to $v$ has weight $65.$ Which of the statements is always true? ... $(u, v) = 12$ Weight of $(u, v) \geq 12$ Nothing can be said about the weight of $(u, v)$
Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has...
go_editor
866
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
shortest-path
+
–
1
votes
2
answers
612
CMI2016-A-1
In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following property: there exists a vertex that is a neighbour of all other vertices. Consider the following statements: If ... say about these statements? Only i is true Only ii is true Both i and ii are true Neither i nor ii is true
In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following proper...
go_editor
1.0k
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
shortest-path
+
–
3
votes
1
answer
613
TIFR CSE 2016 | Part B | Question: 15
Let $G$ be an undirected graph. For a pair $(x, y)$ of distinct vertices of $G$, let $\mathsf{mincut}(x, y)$ be the least number of edges that should be delted from $G$ so that the resulting graph has no $x-y$ ... and iv are possible but neither ii nor iii ii and iv are possible but neither i not iii iii and iv are possible but neither i nor ii
Let $G$ be an undirected graph. For a pair $(x, y)$ of distinct vertices of $G$, let $\mathsf{mincut}(x, y)$ be the least number of edges that should be delted from $G$ s...
go_editor
826
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
+
–
3
votes
4
answers
614
TIFR CSE 2016 | Part B | Question: 13
An undirected graph $G = (V, E)$ is said to be $k$-colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we have $c(u) \neq c(v)$. Which of the following ... degree in $G$ There is a polynomial time algorithm to check if $G$ is $2$-colourable If $G$ has no triangle then it is $3$-colourable
An undirected graph $G = (V, E)$ is said to be $k$-colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we...
go_editor
1.2k
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
graph-theory
graph-coloring
+
–
6
votes
1
answer
615
TIFR CSE 2016 | Part B | Question: 11
Let $n \geq 4$ be an integer. Regard the set $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the following undirected graph $H$ ... inifinite number of vertices The diameter of $H$ is infinite $H$ is conneceted $H$ contains an infinite clique $H$ contains an infinite independent set
Let $n \geq 4$ be an integer. Regard the set $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the following undirected graph $H$.$$ V(H) = \{S \subseteq \math...
go_editor
721
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
+
–
4
votes
1
answer
616
TIFR CSE 2016 | Part B | Question: 10
A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $I \subseteq V(G)$ such that no edge has both its endpoints in $I$. Which of the ... $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set
A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $...
go_editor
813
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
graph-theory
vertex-cover
+
–
7
votes
1
answer
617
TIFR CSE 2016 | Part B | Question: 9
Which of the following graphs DOES NOT have an Eulerian circuit? (Recall that an Eulerian circuit in an undirected graph is a walk in the graph that starts at a vertex and returns to the vertex after traveling on each edge exactly once.) $K_{9, 9}$ $K_{8, 8}$ $K_{12, 12}$ $K_9$ The ...
Which of the following graphs DOES NOT have an Eulerian circuit? (Recall that an Eulerian circuit in an undirected graph is a walk in the graph that starts at a vertex an...
go_editor
2.2k
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
discrete-mathematics
graph-theory
euler-graph
normal
+
–
0
votes
1
answer
618
self doubta
please explain these few point: how is longest path between any pair of vertices different from diameter of a agraph.? in dijkstra algorithm,each edge is relaxed eaxtly one time..is it true or false?
please explain these few point:how is longest path between any pair of vertices different from diameter of a agraph.?in dijkstra algorithm,each edge is relaxed eaxtly one...
Akriti sood
493
views
Akriti sood
asked
Dec 28, 2016
Algorithms
graph-theory
dijkstras-algorithm
true-false
+
–
2
votes
2
answers
619
graph theory
thor
1.3k
views
thor
asked
Dec 28, 2016
Graph Theory
graph-theory
graph-connectivity
euler-graph
+
–
3
votes
3
answers
620
TIFR CSE 2016 | Part A | Question: 14
A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent vertices, and is contained in the interior of the polygon (except for its points). Two such diagonals are said to cross if they have a point in common in the interior of the polygon. In one such ... the information given $\frac{n}{2}-2$ $\frac{n}{4}-1$ $n-4$ $n^2 - 9.5 n +22$
A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent vertices, and is contained in the interior of the polygon (except for its points). Two...
go_editor
874
views
go_editor
asked
Dec 28, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
+
–
3
votes
1
answer
621
Consider an array ‘A’ with 2m elements. The elements in odd position are sorted in non-increasing order that
Consider an array ‘A’ with 2m elements. The elements in odd position are sorted in non-increasing order that is A >= A[3] >= A[5]......A[2m-1] The elements in even p...
Akriti sood
1.0k
views
Akriti sood
asked
Dec 26, 2016
DS
algorithms
sorting
graph-theory
+
–
2
votes
1
answer
622
planar region
How many planar regions? How many closed regions? and how many are unbounded? How many of then are bounded by a cycle of length $4$ ? Now, for example (a different question, not related to above diagram ) a question says, In a connected 3 regular graph, ... region is bounded by exactly 5 edges, then count no of edges? Please explain the last QS with the help of Euler's equation.
How many planar regions?How many closed regions? and how many are unbounded?How many of then are bounded by a cycle of length $4$ ?Now, for example (a different question,...
dd
2.6k
views
dd
asked
Dec 26, 2016
Graph Theory
graph-theory
graph-planarity
+
–
8
votes
5
answers
623
TIFR CSE 2016 | Part A | Question: 2
Consider the graph shown below: The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set of $9$ possibilities. Next, a common neighbour $k$ of $i$ and $j$ is chosen, again uniformly from the set of ... $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$
Consider the graph shown below:The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set...
go_editor
1.1k
views
go_editor
asked
Dec 26, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
probability
+
–
0
votes
0
answers
624
E = 2N -3
I read in https://gateoverflow.in/28955/given-vertex-edges-how-find-non-isomorphic-graphs-possible question explanantion,it was written that e=2n-3 where e= number of edges and n is no of vertices. how is it derived??can anyone tell me the source??
I read in https://gateoverflow.in/28955/given-vertex-edges-how-find-non-isomorphic-graphs-possible question explanantion,it was written that e=2n-3 where e= number of edg...
Akriti sood
157
views
Akriti sood
asked
Dec 24, 2016
Graph Theory
graph-theory
engineering-mathematics
+
–
3
votes
1
answer
625
Bipartite Graph
Is DFS can be applied to check that a graph is bipartite or not?
Is DFS can be applied to check that a graph is bipartite or not?
vaishali jhalani
1.4k
views
vaishali jhalani
asked
Dec 23, 2016
DS
graph-theory
algorithms
+
–
17
votes
2
answers
626
TIFR CSE 2017 | Part B | Question: 13
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if the corresponding edges in $G$ are ... vertex in the line graph is at most the maximum degree in the original graph each vertex in the line graph has degree one or two
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if...
go_editor
2.9k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
bipartite-graph
+
–
54
votes
7
answers
627
TIFR CSE 2017 | Part B | Question: 12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n-1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a d...
go_editor
6.6k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-connectivity
+
–
23
votes
2
answers
628
TIFR CSE 2017 | Part B | Question: 10
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements: If every vertex in $G$ has ... the above statements is/are TRUE? Choose from the following options: only i only i and ii only i and iii only ii and iii i, ii, and iii
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider ...
go_editor
2.8k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
38
votes
4
answers
629
TIFR CSE 2017 | Part B | Question: 1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the f...
go_editor
4.7k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
7
votes
3
answers
630
GATE CSE 1988 | Question: 13iii
Are the two digraphs shown in the above figure isomorphic? Justify your answer.
Are the two digraphs shown in the above figure isomorphic? Justify your answer.
go_editor
1.2k
views
go_editor
asked
Dec 20, 2016
Graph Theory
normal
gate1988
descriptive
graph-theory
graph-isomorphism
out-of-gate-syllabus
+
–
Page:
« prev
1
...
16
17
18
19
20
21
22
23
24
25
26
...
30
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register
