# Recent questions tagged graph-theory

A tree has 14 vertices of degree 1 and degree of each of remaining vertices is 4 or 5. If the tree has ‘n’ vertices then number of vertices with degree 5 is:- (40-2n) (3n-54) (54-2n) (3n-40)
Hi There is 2 book for graph theory so which book is followed because is rosen is short for graph theory and deo is very detailed so for gate which book is followed ? in rosen so there is complete detail for graph theory so if i read rosen so can i make gate related questions or not ? thank you
On a gate paper 2015 set 2 Q26 CS of 2 marks theres a question about self complementary graph, what is the meaning of congruent to 0 mod 4, 1 mod 4
Find the number of paths of length n between any two nonadjacent vertices in K3,3 for the following values of n: a)2 b)3. c)4. d)5 ( i am able to understand the number of paths of length n between any two adjacent vertices in K3,3… but i am not able to get intuition for non adjacent in the adjacency matrix)
1 vote
How many non-isomorphic graphs are possible with 6 edges 6 vertices each having a degree of 2? 2 4 5 6
Please explain the basic difference between Independent set and Dominating Set?
If G is a connected graph containing a cycle c which contains an edge e , then show that G-e is still connected.
1 vote
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between$u$and$v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
1 vote
consider a cycle graph of 4 vertices and needs to perform the vertex coloring using 4 colors. The maximum number of vertex colorings possible is (Answer given as 68)
Suppose that a tree T has N1 vertices of degree 1, 2 vertices of degree 2 , 4 vertices of degree 3 And 3 vertices of degree 4. Number of vertices in the tree is ? Answer given is 21
1 vote
is this statement true? in a graph with unique edge weight the spanning tree of second lowest weight is unique. I am not not able to come up with the example to prove it wrong .
1 vote
Let G be a graph with n vertices and if every vertex has a degree of at least $\frac{n−1}{2}$ then G is connected. Source : https://gateoverflow.in/1221/gate2007-23 Let G be a graph with n vertices and if every vertex has a degree of at least $\frac{n}{2}$ then G is connected. source : https://nptel.ac.in/courses/106/106/106106183/ My doubt : Which one is right?
$K_5$ is non-planar. I am showing you my proof. Please tell me whether this is the right way or not to prove that $K_5$ is non-planar. $\sum$ (deg)$=4+4+4+4+4=20$ $e=10$ and $n=5$ Assume $K_5$ is planar. $v-e+r=2$ $5-10+r=2$ $r=7$ Now ... $K_5$ is non-planar. If this is the right way, why this method didn't work in this graph. Source: https://gateoverflow.in/87129/gate1990-3-vi
How to count number of labeled simple graphs? Please explain!
I was working from the famous book of Deo. Then i found this problem very hard and interesting. Any ideas to give me? - Let us define a new term called edge isomorphism as follows: Two graphs G1 and G2 are edge isomorphic if there is a one-to- ... are also incident in G2. Discuss the properties of edge isomorphism. Construct an example to prove that edge-isomorphic graphs may not be isomorphic.
From Narsingh Deo, Graph Theory -> A round-robin tournament (when every player plays against every other) among n players (n being an even number) can be represented by a complete graph of n vertices. Discuss how you would schedule the tournaments to finish in the shortest possible time.
How many Hamiltonian cycles are there in complete bipartite graph K n,n
S1: A tree with n vertices which has no vertices of degree 2 must have at least leaves S2: The number of trees on 5 labelled vertices is 125. Which of the following statements is true? (A). Only S1 (B). Only S2 (C). Only S1 and S2 (D). None of the above
Consider the following Graphs: S1: Graph with vertices and each vertex has degree S2: Graph with 20 vertices such that for every 2 vertices Which of the following represents hamilton graph? (A). Only S1 (B). Only S2 (C). Both S1 and S2 (D). Neither S1 nor S2
Please tell me what is the Independence Number Domination Number Matching Number Covering Number of the given graph in the picture. Does perfect matching exist in the given graph?
1 vote
The Havell Hakimi Algorithm Requires the sorting of the degree sequence and later marking and subtracting according to that order. Does this means that the vertex with the highest degree will always have an edge with the vertex with the second highest degree (I am assuming ... ? (Also I have noticed that without sorting the algorithm doesn't give correct output so I think it is a necessary step)
The number of possible 3-ordered trees with 5 nodes A,B,C,D,E is ??
Find number of perfect matching in Kn where n is even? Please explain too?
Euler circuit does not exist if no of odd degree vertices is 2 in graph. Why so? And not even Euler path when number of odd degree vertices is 4. Why so?
What is the degree of region r4? How you find it?
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
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______.
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between two nodes ... $\mid i-j \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
Which of the following graphs has an Eulerian circuit? Any $k$-regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above
The maximum number of edges in a n-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
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 number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$
The minimum number of edges in a connected cyclic graph on $n$ vertices is: $n-1$ $n$ $n+1$ None of the above