The Gateway to Computer Science Excellence
0 votes
59 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
in Graph Theory by Junior (961 points) | 59 views
+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 answer this question.

Related questions

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
50,650 questions
56,192 answers
193,988 comments
94,858 users