0 votes 0 votes 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 Chaitrasj asked Jan 16, 2019 Chaitrasj 458 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply aditya333 commented Jan 16, 2019 reply Follow Share 1 seems the most suitable answer 1 votes 1 votes Chaitrasj commented Jan 16, 2019 reply Follow Share 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? 0 votes 0 votes aditya333 commented Jan 16, 2019 reply Follow Share 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 1 votes 1 votes Chaitrasj commented Jan 16, 2019 reply Follow Share 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 0 votes 0 votes aditya333 commented Jan 16, 2019 reply Follow Share 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 1 votes 1 votes Chaitrasj commented Jan 16, 2019 reply Follow Share 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 votes 0 votes Deepalitrapti commented Jun 18, 2019 reply Follow Share C4 is a 2 regular graph and cycle contain then how 1 statement is false? 0 votes 0 votes Please log in or register to add a comment.