menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Recent questions and answers in Graph Theory

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions and answers in Graph Theory

41 votes
7 answers
1
TIFR2017-B-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 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}$
answered 4 hours ago in Graph Theory reboot 3.2k views
1 vote
1 answer
3
Ace Test Series: Graph Theory - Counting
Number of multi-graphs possible with 4 vertices and at most 2 edges between each pair of vertices is ________________
Number of multi-graphs possible with 4 vertices and at most 2 edges between each pair of vertices is ________________
answered Dec 29, 2020 in Graph Theory Karan Negi 338 views
78 votes
9 answers
4
GATE2014-1-51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
answered Dec 17, 2020 in Graph Theory ashutoshbsathe 13.2k views
0 votes
2 answers
5
GAte zeal mock
I got 41 as answer please verify
I got 41 as answer please verify
answered Dec 9, 2020 in Graph Theory eshita1997 209 views
22 votes
5 answers
6
GATE2018-18
The chromatic number of the following graph is _____
The chromatic number of the following graph is _____
answered Dec 6, 2020 in Graph Theory Raj Bopche 5.5k views
46 votes
4 answers
7
GATE2003-8, ISRO2009-53
Let $G$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $G$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$
Let $G$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $G$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$
answered Dec 4, 2020 in Graph Theory StoneHeart 7.7k views
36 votes
4 answers
8
GATE2010-1
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$, then $| S| = 2| T |$ $| S | = | T | - 1$ $| S| = | T | $ $| S | = | T| + 1$
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$, then $| S| = 2| T |$ $| S | = | T | - 1$ $| S| = | T | $ $| S | = | T| + 1$
answered Nov 28, 2020 in Graph Theory StoneHeart 5.8k views
40 votes
4 answers
9
GATE2013-26
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and $e'$ ... graph of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and $e'$ are ... line graph of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only
answered Nov 28, 2020 in Graph Theory StoneHeart 9.1k views
27 votes
4 answers
10
GATE2008-23
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertex-cover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertex-cover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$
answered Nov 28, 2020 in Graph Theory StoneHeart 6k views
60 votes
5 answers
11
GATE2006-72
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$
answered Nov 27, 2020 in Graph Theory StoneHeart 8.6k views
56 votes
5 answers
12
GATE2004-79
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$ $^{\left(\frac{n^2-n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$ $^{\left(\frac{n^2-n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
answered Nov 27, 2020 in Graph Theory StoneHeart 7.4k views
48 votes
10 answers
14
GATE1994-1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
answered Oct 31, 2020 in Graph Theory rupesh17 17.1k views
22 votes
5 answers
15
GATE2015-1-54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
answered Oct 27, 2020 in Graph Theory prajjwalsingh_11 9.2k views
37 votes
5 answers
16
GATE2001-2.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2} $
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2} $
answered Oct 25, 2020 in Graph Theory varunrajarathnam 7.4k views
1 vote
4 answers
17
NIELIT 2017 DEC Scientist B - Section B: 52
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
answered Oct 24, 2020 in Graph Theory debasish paramanik 947 views
4 votes
2 answers
18
Graph Theory conceptual
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree ... a vertex of degree 7. Which of the following can be the degree of the last vertex? (A) 3 (B) 0 (C) 5 (D) 4
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of ... 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex? (A) 3 (B) 0 (C) 5 (D) 4
answered Oct 14, 2020 in Graph Theory ayush.5 285 views
2 votes
2 answers
22
Made easy Test Series:Graph Theory+Automata
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... $x$ and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
answered Oct 13, 2020 in Graph Theory arun yadav 364 views
24 votes
3 answers
23
GATE1990-3-vi
Which of the following graphs is/are planner?
Which of the following graphs is/are planner?
answered Oct 2, 2020 in Graph Theory codeitram 3.1k views
6 votes
3 answers
24
GATE1988-2xvi
Write the adjacency matrix representation of the graph given in below figure.
Write the adjacency matrix representation of the graph given in below figure.
answered Oct 2, 2020 in Graph Theory codeitram 1.6k views
25 votes
6 answers
26
TIFR2018-A-9
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$
answered Sep 26, 2020 in Graph Theory manish_pal_sunny 2.3k views
26 votes
4 answers
27
GATE2008-IT-3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
answered Sep 26, 2020 in Graph Theory manish_pal_sunny 3.9k views
7 votes
5 answers
29
ISRO2011-35
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1) - k$ $(v+1)/2 - k$ $v - k$ $v + k$
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1) - k$ $(v+1)/2 - k$ $v - k$ $v + k$
answered Sep 18, 2020 in Graph Theory Dhruvil 2.9k views
0 votes
2 answers
30
NIELIT 2017 July Scientist B (IT) - Section B: 2
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 ... Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
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.
answered Sep 18, 2020 in Graph Theory Dhruvil 1.6k views
9 votes
3 answers
31
GATE1987-9c
Show that the number of odd-degree vertices in a finite graph is even.
Show that the number of odd-degree vertices in a finite graph is even.
answered Sep 15, 2020 in Graph Theory KUSHAGRA गुप्ता 738 views
30 votes
4 answers
32
GATE2002-1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
answered Sep 14, 2020 in Graph Theory Nishisahu 5.8k views
1 vote
1 answer
35
NIELIT 2017 DEC Scientific Assistant A - Section B: 38
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$
asked Mar 31, 2020 in Graph Theory Lakshman Patel RJIT 228 views
0 votes
2 answers
36
NIELIT 2016 MAR Scientist B - Section B: 1
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$
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 412 views
1 vote
1 answer
38
NIELIT 2016 DEC Scientist B (CS) - Section B: 5
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$
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 207 views
0 votes
1 answer
39
NIELIT 2017 July Scientist B (IT) - Section B: 1
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 1.9k views
0 votes
1 answer
40
NIELIT 2017 July Scientist B (IT) - Section B: 3
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 380 views
To see more, click for all the questions in this category.
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...