search
Log In

Recent questions and answers in Engineering Mathematics

0 votes
2 answers
1
0 votes
1 answer
2
0 votes
3 answers
3
0 votes
1 answer
4
Which of the following is true? The size of the maximum independent set on G is the same as the size of maximum clique on G'(Complement of G) The size of minimum vertex cover on G is the same as the size of maximum clique on G'(complement of G) The size of minimum vertex cover on G is the same as the size of maximum clique on G'
answered 1 day ago in Graph Theory Deepakk Poonia (Dee) 150 views
0 votes
3 answers
5
The complete graph with four vertices has $k$ edges where $k$ is : $3$ $4$ $5$ $6$
answered 2 days ago in Graph Theory Hira Thakur 3.5k views
26 votes
3 answers
6
In an undirected graph $G$ with $n$ vertices, vertex $1$ has degree $1$, while each vertex $2,\ldots,n-1$ has degree $10$ and the degree of vertex $n$ is unknown, Which of the following statement must be TRUE on the graph $G$? There is a path from vertex $1$ ... $n$ has degree $1$. The diameter of the graph is at most $\frac{n}{10}$ All of the above choices must be TRUE
answered 2 days ago in Graph Theory rish1602 2.7k views
28 votes
4 answers
8
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is: $12$ $8$ less than $8$ more than $12$
answered 4 days ago in Graph Theory rish1602 5.6k views
34 votes
6 answers
9
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.
answered 4 days ago in Graph Theory rish1602 2.9k views
35 votes
5 answers
10
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph is sure to be regular complete Hamiltonian Euler
answered 4 days ago in Graph Theory rish1602 7.2k views
32 votes
5 answers
11
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 4 days ago in Graph Theory rish1602 6.7k views
32 votes
4 answers
12
33 votes
7 answers
13
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$ I and II III and IV IV only II and IV
answered 4 days ago in Graph Theory rish1602 10.3k views
2 votes
2 answers
14
1 vote
2 answers
15
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Compute the following$: M(101)$
answered 5 days ago in Calculus Hira Thakur 135 views
1 vote
2 answers
16
1 vote
3 answers
17
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. Show that any finite simple graph has at least two vertices with the same degree.
answered 6 days ago in Graph Theory soujanyareddy13 301 views
14 votes
3 answers
18
A complete graph on $n$ vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let $G$ be a complete graph on $10$ vertices. Let $u$, $v$, $ w$ be three distinct vertices in $G$. How many simple paths are there from $u$ to $v$ going through $w$?
answered 6 days ago in Graph Theory soujanyareddy13 1.6k views
38 votes
10 answers
20
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
answered May 7 in Graph Theory rish1602 7.3k views
50 votes
9 answers
21
16 votes
4 answers
22
Consider the following two statements. There are infinitely many interesting whole numbers. There are finitely many uninteresting whole numbers. Which of the following is true? Statements $1$ and $2$ are equivalent. Statement $1$ implies statement $2$. Statement $2$ implies statement $1$. None of the above.
answered May 7 in Mathematical Logic soujanyareddy13 956 views
17 votes
4 answers
23
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 ... of degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$
answered May 7 in Graph Theory soujanyareddy13 3.3k views
12 votes
5 answers
24
$10\%$ of all email you receive is spam. Your spam filter is $90\%$ reliable: that is, $90\%$ of the mails it marks as spam are indeed spam and $90\%$ of spam mails are correctly labeled as spam. If you see a mail marked spam by your filter, what is the probability that it really is spam? $10\%$ $50\%$ $70\%$ $90\%$
answered May 7 in Probability soujanyareddy13 3k views
10 votes
3 answers
25
The $12$ houses on one side of a street are numbered with even numbers starting at $2$ and going up to $24$. A free newspaper is delivered on Monday to $3$ different houses chosen at random from these $12$. Find the probability that at least $2$ of these newspapers are delivered to houses with numbers strictly greater than $14$. $\frac{7}{11}$ $\frac{5}{12}$ $\frac{4}{11}$ $\frac{5}{22}$
answered May 7 in Probability soujanyareddy13 1.1k views
19 votes
3 answers
26
For the inter-hostel six-a-side football tournament, a team of $6$ players is to be chosen from $11$ players consisting of $5$ forwards, $4$ defenders and $2$ goalkeepers. The team must include at least $2$ forwards, at least $2$ defenders and at least $1$ goalkeeper. Find the number of different ways in which the team can be chosen. $260$ $340$ $720$ $440$
answered May 7 in Combinatory soujanyareddy13 1.2k views
2 votes
2 answers
27
Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements: There is a vertex of degree smaller than $8$ in $G$. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it. Which of the following is true: I Only II Only Both I and II Neither I nor II
answered May 7 in Graph Theory soujanyareddy13 425 views
1 vote
1 answer
28
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$.
answered May 7 in Graph Theory soujanyareddy13 117 views
1 vote
2 answers
29
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$.
answered May 7 in Graph Theory soujanyareddy13 143 views
4 votes
2 answers
30
Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following is true? $s=99$ $s=198$ $99 \: < \: s \: < \: 198$ None of the above
answered May 7 in Graph Theory fib(x) 401 views
2 votes
2 answers
31
Let $A=\begin{pmatrix} 1 & 1 & 0\\ 0 & a & b\\1 & 0 & 1 \end{pmatrix}$. Then $A^{-1}$ does not exist if $(a,b)$ is equal to $(1,-1)$ $(1,0)$ $(-1,-1)$ $(0,1)$
answered May 6 in Linear Algebra eshita1997 169 views
4 votes
3 answers
32
The school athletics coach has to choose $4$ students for the relay team. He calculates that there are $3876$ ways of choosing the team if the order in which the runners are placed is not considered. How many ways are there of choosing the team if the order of the runners is to be ... Between $12,000$ and $25,000$ Between $75,000$ and $99,999$ Between $30,000$ and $60,000$ More than $100,000$
answered May 6 in Combinatory soujanyareddy13 259 views
10 votes
3 answers
33
You arrive at a snack bar and you can't decide whether to order a lime juice or a lassi. You decide to throw a fair $6$-sided die to make the choice, as follows. If you throw $2$ or $6$ you order a lime juice. If you throw a $4$, you order a lassi. Otherwise, you throw the die ... is the probability that you end up ordering a lime juice? $\frac{1}{3}$ $\frac{1}{2}$ $\frac{2}{3}$ $\frac{3}{4}$
answered May 6 in Probability soujanyareddy13 620 views
15 votes
2 answers
34
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What is the degree of vertex $10$ ? $5$ $6$ $7$ $8$
answered May 6 in Graph Theory soujanyareddy13 840 views
3 votes
2 answers
35
Suppose each edge of an undirected graph is coloured using one of three colours - red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not an endpoint ... an endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. (A) and (C).
answered May 6 in Graph Theory soujanyareddy13 245 views
5 votes
2 answers
36
A binary relation $R ⊆ (S S)$ is said to be Euclidean if for every $a, b, c ∈ S, (a, b) ∈ R$ and $(a, c) ∈ R$ implies $(b, c) ∈ R$. Which of the following statements is valid? If $R$ is Euclidean, $(b, a) ∈ R$ and $(c, a) ∈ R$, then $(b, c) ∈ R$, for every $a, b, c ∈ S$ ... $R$ is Euclidean, $(a, b) ∈ R$ and $(b, c) ∈ R$, then $(a, c) ∈ R$, for every $a, b, c ∈ S$ None of the above.
answered May 6 in Set Theory & Algebra soujanyareddy13 341 views
6 votes
2 answers
37
Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes-for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that there are infinitely many twin primes. Let $\text{TwinPrime}(n)$ be a predicate that is true if $n$ ... $\exists m \cdot \forall n \cdot \text{TwinPrime}(n) \text{ implies }n \leq m$
answered May 6 in Mathematical Logic soujanyareddy13 469 views
2 votes
2 answers
38
Consider a social network with $n$ persons. Two persons $A$ and $B$ are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons $F_1, \dots, F_m$ such that $A$ and $F_1$ ... friends. It is known that there are $k$ persons such that no pair among them is connected. What is the maximum number of friendships possible?
answered May 6 in Combinatory soujanyareddy13 254 views
1 vote
1 answer
39
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Give a constant time algorithm that computes $M(n)$ on input $n$. (A constant-time algorithm is one whose running time is independent of the input $n$)
answered May 6 in Calculus soujanyareddy13 101 views
1 vote
2 answers
40
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.
answered May 6 in Graph Theory soujanyareddy13 319 views
To see more, click for all the questions in this category.
...