Awesome q2a theme
0 votes
29 views

What will be the number of components?

ago in Graph Theory by (79 points) | 29 views

1 Answer

+1 vote
Best answer

(d). None of these 

When we divide a number by 4, the remainder can lie from 0 to 3.

Now vertices with label x, s.t. x % 4 = 0 will form a single component.

Vertices with label x, s.t. x % 4 = 2 will form a single component [4m + 2 + 4n + 2 = 4(m + n + 1)].

Vertices with label x, s.t. x % 4 = 1 or x % 4 = 3 will form a single component [4m + 1 + 4n + 3 = 4(m + n + 1)].

You can take a simple example with n = 2, and look at the options too.

 

ago by (2.9k points)
selected ago by
0
I didn't understand the 4m + 2 + 4n +2.
+1
Suppose there are two different numbers which leave a remainder of 2 when divided by 4, e.g 2 and 6 they will form a single component as 2 + 6 = 8 which is divisible by 4.
0
Ok, got it. So did you get the number of components '3' after drawing or is there a formula or some concept that I'm missing.
+1
After drawing, even if there is a formula you should avoid because it would be useless anyway.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,968 questions
3,119 answers
14,341 comments
95,792 users