GATE Breaker

Havel-Hakimi Theorem In this tutorial, we will learn how to determine if a given degree sequence can form a simple graph using Havel-Hakimi theorem . A graph is said to be a simple graph if it has no self-loop and parallel edges. For a given graph, it is always possible to find its degree sequence, but it may or may not be possible to draw a graph for a given degree sequence.  A degree sequence is called a  graphic sequence  if a simple graph can be drawn with that sequence. For example, the degree sequence <2, 2, 2> is graphic.  Theorem:  The nonincreasing sequence $<d_1, d_2, \ldots, d_n>$ is graphic if and only if the sequence $(d_2-1,d_3-1, \ldots, d_{d_1+1}-1, d_{d_1+2}, d_{d_1+3}, \ldots, d_n)$ is also graphic.  Note: A sequence with all zeroes is always graphic because we can draw that many isolated vertices.  Based on the above theorem, we can use the following algorithm to draw a simple graph from a given degree sequenc...

How many distinct binary search trees can be created out of 4 distinct keys?  (GATE 2005)  (A) 5  (B) 14   (C) 24   (D) 42  Answer: (B) 14  Explanation:  Here, number of keys, $k = 4$.  Therefore, the number of distinct binary search trees that can be formed out of 4 distinct keys is  $= \dfrac{^{2k}C_k}{k + 1}$  $ = \dfrac{^{8}C_4}{5}$  $= 14$ 

How many undirected graphs (not necessarily connected) can be constructed out of a given set $V = \{v_1, v_2, \ldots, v_n\}$ of $n$ vertices? (GATE 2001) (A) $\frac{n(n-1)}{2}$, (B) $2^n$, (C) $n!$, (D) $2^{\frac{n(n-1)}{2}}$  Answer: (D) $2^{\frac{n(n-1)}{2}}$  Explanation:  Here, number of vertices = $n$.  Therefore, $^nC_2 = \frac{n(n-1)}{2}$ number of edges can be formed.  Now, each subset of these edges can form an undirected graph (not necessarily connected).  Therefore, total $2^{\frac{n(n-1)}{2}}$ number of graphs can be formed.  Next Post