Test: Graph Theory- 1 - Computer Science Engineering (CSE) MCQ

K₅ is smallest non-planar graph in terms of number of vertices.
The number of vertices in K₅ is 5 and number of edges in 

The graph containing maximum number of edges in a n-node undirected graph without self loops is complete graph.
The number of edges in complete graph with n-node, 

An assignment of the colors 1,2,3 and 4 to the vertices of the graph is shown below such that the graph is properly colored.

So 4 colours are required.
[Note: The graph is a planar graph. The four colour theorem says that the chromatic number of a planar graph is at most = 4]

Acyclic graph are graphs which does not contain cycle.
For maximum number of edges each vertex connect to other vertex only if it does not from a cycle i.e. from a tree with n vertices, which has maximum 77-1 edges. Ex. with 4 vertices, 3 edges maximum.

G₁ is same as K_{3 3} which is known to be non planar G₂, G₃ and G₄ can be redrawn as follows so that they are planar.

K₅ and K_{3, 3} are the smallest non planar graphs. K₅ has 5 vertices and ⁵C₂ = 10 edges and K_{3, 3} has 6 vertices and 3 x 3 = 9 edges . So, the non planar graph with minimum number of edges is K_{3, 3} with 9 edges and 6 vertices.
[Note: K₅ is the non planar graph with minimum number of vertices]

In a simple connected undirected graph (with more than two vertices), at least 2 vertices must have same degree, since if this is not true, then all vertices would have different degrees, A graph with all vertices having different degrees is not possible to construct (can be proved as a corollary to the Havell-Hakimi theorem). Notice that it is possible to construct graphs satisfying choices a, c and d.

A tree with 1 node is not possible, since it is given that every node has exactly 1 child.
Now consider a tree with 2 nodes (a is the root)

Now a has exactly one child. Number of descendents of a = 2. But this contradicts the given fact that every node has an odd number of descendents.
Now consider atree with 3 nodes. Since, every- node has exactly one child, it must be of the form,

Here a has 3 descendents, b has 2 descendents and c has one. Again we have contradiction in that b does not have odd number of descendents. Similarly can show that for tree with 4, 5, 6 ... nodes, it is not possible to have all nodes with odd number of descendents! So correct answer is the tree has 0 nodes, i.e., choice (a).

Havell-Hakimi algorithm can be used to check whether a given degree sequence is a graph or not.
The algorithm is
1. Remove top node of the sequence.
2. Subtract "1" from as m any nodes in remaining sequence as the degree of top node that was removed.
3. Rearrange this sequence in non increasing order.
4. Check if resulting sequence is a graph.
5. Proceed again to step 1.
If the given sequence is not a graph we will see a violation in step 4, such as presence of negative degrees in the sequence. Otherwise the algorithm will bottom out with a degree sequence consisting of only even number of 1 ’s and any number of 0’s.
Now applying the algorithm to the degree sequences I, II, III and IV, one by one:


The sequence is not a graph (Step 4), since negative degrees not possible in a valid graph. So, algorithm ends.
II is cannot be the degree sequence of any graph. Similarly we can show that III is degree sequence of some graph and IV is not a degree sequence of any graph.

The planar embedding of K₄ and Q₃ is shown below:


So both graphs are planar.