The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Ace Academy Test series
0
votes
58
views
If a 2 regular graph G has a perfect matching, then which of the following is NOT true?
1. G is a cycle graph
2. Chromatic number of G is 2
3. Every component of G is even cycle
4. G is a bipartite graph
asked
Jan 16
in
Graph Theory
by
Chaitrasj
Junior
(
953
points)

58
views
answer
comment
+1
1 seems the most suitable answer
0
Yes answer given is1st option
Why can't option 3 be answer? Why there will be a component of even cycle always?
Can you give some explanation like how you arrived at your answer?
+1
for perfect matching the necessary condition is the no of vertices should be even.
the graph being 2 regular implies the no of edges =no of vertices.
therefore the no of edges is even
having a graph with odd cycle violates the above conditions
0
Yes your explanation is right. But if every component of G is always an even cycle, means it's a cycle graph right... So how option 1 is becoming False under any certain case :(
What's the difference between option 1 and 3, I'm confused among them
+1
from my understanding a cycle graph consists of a single cycle.But our graph can contain multiple cycles and components.Hence 1 is the most suitable option
0
Yess we can have a graph with 2 components such that each component is $C_4$. In this case all other options are true, but 1 is becoming False it's not a cycle graph.. Thanks!
0
C4 is a 2 regular graph and cycle contain then how 1 statement is false?
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
0
Answers
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
+2
votes
3
answers
1
ACE ACADEMY BOOKLET QUESTION
Let $G$ $=$ $(V, E)$ be a simple nonempty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two nonempty and nonoverlapping subsets $S$ and $T$. Which of the following is true? There are at least two edges that ... $S$ and one end point in $T$ There are exactly one edge that have one end point in $S$ and one end point in $T$
asked
May 26
in
Graph Theory
by
`JEET
Loyal
(
8k
points)

110
views
+2
votes
3
answers
2
Ace academy booklet #graph theory
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Euler circuit exists $\Leftrightarrow$ $n$ is odd. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Euler circuit exists ... Euler circuit exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Euler circuit exits $\Leftrightarrow$ $n$ is even.
asked
May 26
in
Graph Theory
by
`JEET
Loyal
(
8k
points)

60
views
+1
vote
1
answer
3
ACE ACADEMY BOOKLET
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Hamiltonian cycle exists for all n. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Hamiltonian cycle exists $\Leftrightarrow$ ... Hamiltonian cycle exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.
asked
May 26
in
Graph Theory
by
`JEET
Loyal
(
8k
points)

59
views
graphtheory
discretemathematics
0
votes
1
answer
4
ace academy test series toc turing machine
asked
May 28
in
Theory of Computation
by
hitesh159
(
141
points)

113
views
theoryofcomputation
turingmachine
acetestseries
0
votes
0
answers
5
Ace Academy Test series
Consider the multi selection problem: Given a set 'S' of n elements and set 'K' of 'r' ranks $K_{1}$, $K_{2}$, ....$K_{r}$. Find the $K_1^{th}$, $K_2^{th}$, ....$K_r^{th}$ ... The time complexity of the most efficient algorithm to solve this problem is A. O(n.r) B. O($n^2$.log r) C. O(n) D. O(n.log r)
asked
Jan 11
in
Algorithms
by
Chaitrasj
Junior
(
953
points)

51
views
0
votes
1
answer
6
Ace academy test series
Ans:C. Please explain
asked
Dec 28, 2018
in
Combinatory
by
amitqy
Active
(
1.8k
points)

132
views
settheory&algebra
permutationandcombination
testseries
0
votes
0
answers
7
Ace Academy test series
asked
Dec 26, 2018
in
CO and Architecture
by
amitqy
Active
(
1.8k
points)

25
views
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
Recent Posts
Standard Book Exercise Questions for Computer Science
Resource to Learn Graph Theory Interactively
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Discrete Mathematics
5.1k
Mathematical Logic
2.1k
Set Theory & Algebra
1.3k
Combinatory
879
Graph Theory
805
Probability
987
Linear Algebra
682
Calculus
493
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.6k
Others
1.8k
Admissions
595
Exam Queries
576
Tier 1 Placement Questions
23
Job Queries
72
Projects
17
Follow @csegate
Recent Blog Comments
Are the answers also present ?
@Arjun sir , Is there any page or something where...
@arjun sir but u called about providing the pdfs...
But anyhow I appreciate this. The questions of...
All these PYQ blogs and standard videos blogs...
50,376
questions
55,836
answers
192,558
comments
91,336
users