Test: Graphs Theory- 2 - Computer Science Engineering (CSE) MCQ

Each component will have n/k vertices (pigeonhole principle). Hence, for each component there will be (n/k)-1 edges. Since there are k components, total number of edges= k*((n/k)-1) = n-k.

Euler's formula for planar graphs:

v − e + f = 2.

v => Number of vertices
e => Number of edges
f => Number of faces

Since degree of every vertex is at least 3, below is true from handshaking lemma (Sum of degrees is twice the number of edges)

3v >= 2e
3v/2 >= e

Putting these values in Euler's formula.
v - 3v/2 + f >= 2

f >= v/2 + 2

There are n nodes which are single and 1 node which belong to empty set. And since they are not having 2 or more elements so they won’t be connected to anyone hence total number of nodes with degree 0 are n+1 hence answer should be none. Thanks to roger for the explanation.

n+1 nodes of the graph not connected to anyone as explained in question 70 while others are connected so total number of connected components are n+2 (n+1 connected components by each of the n+1 vertices plus 1 connected component by remaining vertices)

An undirected graph is called a planar graph if it can be drawn on a paper without having two edges cross and such a drawing is called Planar Embedding. We say that a graph can be embedded in the plane, if it planar. A planar graph divides the plane into regions (bounded by the edges), called faces. Graph K4 is palanar graph, because it has a planar embedding as shown in figure below.

Euler's Formula : For any polyhedron that doesn't intersect itself (Connected Planar Graph),the • Number of Faces(F) • plus the Number of Vertices (corner points) (V) • minus the Number of Edges(E) , always equals 2. This can be written: F + V − E = 2. Solution : Here as given, F=?,V=13 and E=19 -> F+13-19=2 -> F=8 So Answer is (B).

Background Explanation: Vertex cover is a set S of vertices of a graph such that each edge of the graph is incident to at least one vertex of S. Independent set of a graph is a set of vertices such that none of the vertices in this set have an edge connecting them i.e. no two are adjacent. A single vertex is an independent set, but we are interested in maximum independent set, that is largest set which is independent set. Relation between Independent Set and Vertex Cover : An interesting fact is, the number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set. How? removing all vertices of minimum vertex cover leads to maximum independent set. So if S is the size of minimum vertex cover of G(V,E) then the size of maximum independent set of G is |V| - S. Solution: size of minimum vertex cover = 8 size of maximum independent set = 20 - 8 =12 Therefore, correct answer is (A). References : vertex cover maximum independent set.

A graph is planar if it can be redrawn in a plane without any crossing edges. G1 is a typical example of nonplanar graphs.

Suppose shortest path from A->B is 6, but in MST, we have A->C->B (A->C = 4, C->B = 3), then along the path in MST, we have minimum congestion, i.e 4

Two vertices are said to be adjacent if they are directly connected, i.e., there is a direct edge between them. So, here, we can assign same color to 1 & 2 (red), 3 & 4 (grey), 5 & 7 (blue) and 6 & 8 (brown). Therefore, we need a total of 4 distinct colors. Thus, C is the correct choice. 
  
Please comment below if you find anything wrong in the above post.

Minimum: The removed vertex itself is a separate connected component. So removal of a vertex creates k-1 components. Maximum: It may be possible that the removed vertex disconnects all components. For example the removed vertex is center of a star. So removal creates n-1 components.

A perfect matching, every vertex of the graph is incident to exactly one edge of the matching. A perfect matching is therefore a matching of a graph containing n/2 edges, the largest possible, meaning perfect matchings are only possible on graphs with an even number of vertices. 

Let the min-degree of G be x, then G has at least |v| *x/2 edges. |v|*x/2 <= 3* |v| -6 for x=6, we get 0 <= -6, Therefore, min degree of G cannot be 6. Hence answer is (D).

We need 3 colors to color a odd cycle and 2 colors to color an even cycle.

Background required - Basic Combinatorics Since the given graph is undirected, that means the order of edges doesn't matter. Since we have to insert an edge between all possible pair of vertices, therefore problem reduces to finding the count of the number of subsets of size 2 chosen from the set of vertices. Since the set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n,2) (also known as "n choose 2"). Using the formula for binomial coefficients, C(n,2) = n(n-1)/2.

Euler's formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, then

v − e + f = 2.
v -> Number of vertices
e -> Number of edges
f -> Number of faces

As per the question v = 10 And number of edges on each face is three Therefore, 2e = 3f [Note that every edge is shared by 2 faces]

Putting above values in v − e + f = 2
10 - e + 2e/3 = 2
e = 3*10 - 6 = 24

An n-vertex self-complementary graph has exactly half number of edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3. Since n(n −1) must be divisible by 4, n must be congruent to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary. 

A bridge in a graph cannot be a part of cycle as removing it will not create a disconnected graph if there is a cycle.

The idea is to use Handshaking Lemma :- In any graph, the sum of all the vertex-degree is equal to twice the number of edges.

Let x = Number of vertices of degree 3.
By Handshaking Lemma
6*2 + 3*4 + (x-9)*3 = 27*2
24 + (x-9)*3 = 54
x-9 = 10
x = 19

A planar graph is a graph on a plane where no two edges are crossing each other. The set of regions of a map can be represented more abstractly as an undirected graph that has a vertex for each region and an edge for every pair of regions that share a boundary segment. Hence the four color theorem is applied here. Here is a property of a planar graph that a planar graph does not require more than 4 colors to color its vertices such that no two vertices have same color. This is known four color theorem.

As here we want subset of edges that connects all the vertices and has minimum total weight i.e. Minimum Spanning Tree Option A - includes cycle, so may or may not connect all edges. Option B - has no relevance to this question. Option C - includes cycle, so may or may not connect all edges. Related: