• Support PF! Buy your school textbooks, materials and every day products Here!

Cubic graph containing a 1-factor

  • Thread starter Robb
  • Start date
221
8
Homework Statement
Does there exist a cubic graph with three bridges that contains a 1-factor?
Homework Equations
##k_0 (G-S) \leq |S|
I understand how to show a given graph does/does not contain a 1-factor but I'm not sure how to show existence (or the lack thereof). Please advise.
 

WWGD

Science Advisor
Gold Member
4,780
2,116
Please define 'factor' here. I am familiar with the concept of Bridges but not with the concept of factors. And maybe you can add tags at the end of your expression so the Latex can render?
 
221
8
1-factor is the same as a perfect matching-A graph G has a perfect matching iff for ##S \in V(G), k_o(G-S) \leq |S|##. If G has odd order, then G has no 1-factor. A 1-factor is a 1-regular sub-graph of G.
Also, every bridgeless cubic graph contains a 1-factor as well as every cubic graph with at most two bridges contains a 1-factor.
 

Want to reply to this thread?

"Cubic graph containing a 1-factor" You must log in or register to reply here.

Related Threads for: Cubic graph containing a 1-factor

Replies
1
Views
2K
Replies
4
Views
4K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
916
  • Last Post
Replies
5
Views
10K
  • Last Post
Replies
3
Views
530
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
5
Views
1K
Top