search
Log In

Recent questions and answers in Graph Theory

41 votes
7 answers
1
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
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
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
22 votes
5 answers
6
46 votes
4 answers
7
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
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
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
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
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
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
22 votes
5 answers
15
37 votes
5 answers
16
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
4 votes
2 answers
18
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
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
6 votes
3 answers
24
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
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
7 votes
5 answers
29
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
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
30 votes
4 answers
32
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
0 votes
2 answers
36
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
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
0 votes
1 answer
40
To see more, click for all the questions in this category.
...