Graph Theory

Question

Every 3-regular graph has a perfect matching?

True or false?

Comments

false...

---

check my answer.

Answer 1

Complete Graph ( K_n )  :-

Every node is adjacent to other node in the graph.

 ===> Degree of any node = n-1 , where n is no.of nodes.

 

Theorem :- Every Complete graph has a perfect matching iff no.of vertices is even

 

Why?

(Matching means 1 node can map atmost 1 node only) if no.of nodes=odd, one vertex should be can't match

 

What is i-regular graph?

every node degree = i in the graph ====> K_(i+1) graph

For existing Perfect Matching i+1 should be even number.

given that 3-regular graph ===> 3+1 = 4 which is even ===> Has a perfect Matching.

Comments

@srestha

mam, i didn't understood that proof, if you understood, can you simplify it?

---

I think

this line telling everything

The Kneser graph  is a generalization of the odd graph, with  corresponding to .

but it will be not a requirement of gate :) 

---

but it will be not a requirement of gate :) 

ok... but learning the concept deeply (especially in Graph theory) is very helpful in the Future of CS ( in research area.)