86 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
1
1 seems the most suitable answer
0

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?

## Related questions

1
198 views
Let $G$ $=$ $(V, E)$ be a simple non-empty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two non-empty and non-overlapping subsets $S$ and $T$. Which of the following is true? There are at least two edges that have one endpoint in ... point in $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$
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 $\Leftrightarrow$ m and n ... $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Euler circuit exits $\Leftrightarrow$ $n$ is even.
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$ $m$ $=$ $n$ ... $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.