Dgdrxrt

What does the "x" in "x86" represent?

String `!23` is replaced with `docker` in command line

Is it fair for a professor to grade us on the possession of past papers?

In predicate logic, does existential quantification (∃) include universal quantification (∀), i.e. can 'some' imply 'all'?

What does an IRS interview request entail when called in to verify expenses for a sole proprietor small business?

Why do we bend a book to keep it straight?

List *all* the tuples!

What is Arya's weapon design?

Fundamental Solution of the Pell Equation

How widely used is the term Treppenwitz? Is it something that most Germans know?

At the end of Thor: Ragnarok why don't the Asgardians turn and head for the Bifrost as per their original plan?

Novel: non-telepath helps overthrow rule by telepaths

Is the Standard Deduction better than Itemized when both are the same amount?

2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?

First console to have temporary backward compatibility

What is the logic behind the Maharil's explanation of why we don't say שעשה ניסים on Pesach?

How do pianists reach extremely loud dynamics?

How do I keep my slimes from escaping their pens?

How do I stop a creek from eroding my steep embankment?

Withdrew £2800, but only £2000 shows as withdrawn on online banking; what are my obligations?

Should I use a zero-interest credit card for a large one-time purchase?

Why are both D and D# fitting into my E minor key?

Why didn't this character "real die" when they blew their stack out in Altered Carbon?

The logistics of corpse disposal

Question regarding perfect matchings in a graph

1

$begingroup$

I have a connected, bridgeless graph with 72 vertices of degree 3 and 2 vertices of degree 2. Is there a way that I can prove that this graph has a perfect matching?

From the graph I can see there is a perfect matching, but I would like to obtain it by a proof without getting from the drawing. (Even by thinking of a general case, like a connected, bridgeless graph has k number of vertices of degree 3, where k is even and 2 vertices of degree 2. Then can we prove that it has a perfect matching?)

Please help me with this question.

Thanks a lot in advance.

Attached below is the mentioned graph. Please consider that the point marked as 52, enclosed in a square is not a part of the graph. Is there any suggestion to prove that this graph is bridgeless (if I do not know its bridgeless)?

graph-theory connectedness matching-theory

share|cite|improve this question

edited Apr 10 at 8:19

Buddhini Angelika

asked Apr 1 at 9:02

Buddhini AngelikaBuddhini Angelika

13611

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  How do you manage to draw the graph?
  $endgroup$
  – mathpadawan
  Apr 9 at 4:05
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @mathpadawan This is actually from a Cayley graph of a semidirect product of two finite groups. I drew that graph using points obtained in GAP and I am experimenting by deleting vertices, so I ended up with above mentioned graph :)
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 4:19
  

  
  
  
  

add a comment | 

1

$begingroup$

I have a connected, bridgeless graph with 72 vertices of degree 3 and 2 vertices of degree 2. Is there a way that I can prove that this graph has a perfect matching?

From the graph I can see there is a perfect matching, but I would like to obtain it by a proof without getting from the drawing. (Even by thinking of a general case, like a connected, bridgeless graph has k number of vertices of degree 3, where k is even and 2 vertices of degree 2. Then can we prove that it has a perfect matching?)

Please help me with this question.

Thanks a lot in advance.

Attached below is the mentioned graph. Please consider that the point marked as 52, enclosed in a square is not a part of the graph. Is there any suggestion to prove that this graph is bridgeless (if I do not know its bridgeless)?

graph-theory connectedness matching-theory

share|cite|improve this question

edited Apr 10 at 8:19

Buddhini Angelika

asked Apr 1 at 9:02

Buddhini AngelikaBuddhini Angelika

13611

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  How do you manage to draw the graph?
  $endgroup$
  – mathpadawan
  Apr 9 at 4:05
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @mathpadawan This is actually from a Cayley graph of a semidirect product of two finite groups. I drew that graph using points obtained in GAP and I am experimenting by deleting vertices, so I ended up with above mentioned graph :)
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 4:19
  

  
  
  
  

add a comment | 

$begingroup$

I have a connected, bridgeless graph with 72 vertices of degree 3 and 2 vertices of degree 2. Is there a way that I can prove that this graph has a perfect matching?

From the graph I can see there is a perfect matching, but I would like to obtain it by a proof without getting from the drawing. (Even by thinking of a general case, like a connected, bridgeless graph has k number of vertices of degree 3, where k is even and 2 vertices of degree 2. Then can we prove that it has a perfect matching?)

Please help me with this question.

Thanks a lot in advance.

Attached below is the mentioned graph. Please consider that the point marked as 52, enclosed in a square is not a part of the graph. Is there any suggestion to prove that this graph is bridgeless (if I do not know its bridgeless)?

graph-theory connectedness matching-theory

share|cite|improve this question

edited Apr 10 at 8:19

Buddhini Angelika

asked Apr 1 at 9:02

Buddhini AngelikaBuddhini Angelika

13611

$endgroup$

share|cite|improve this question

edited Apr 10 at 8:19

Buddhini Angelika

asked Apr 1 at 9:02

Buddhini AngelikaBuddhini Angelika

13611

share|cite|improve this question

edited Apr 10 at 8:19

Buddhini Angelika

asked Apr 1 at 9:02

Buddhini AngelikaBuddhini Angelika

13611

asked Apr 1 at 9:02

Buddhini AngelikaBuddhini Angelika

13611

asked Apr 1 at 9:02

Buddhini AngelikaBuddhini Angelika

13611

1 Answer
1

active

oldest

votes

1

$begingroup$

If the two degree 2 vertices are not connected, connect them by an edge and apply Peterson's theorem and use the fact that you can pick any edge and there will be a perfect matching without that edge. Else, say the edge connecting them is $uv$, subdivide it and add a new vertex $S$ as in the following picture. So apply Peterson on the resulting graph with $SW$ removed!?

share|cite|improve this answer

edited Apr 10 at 0:59

answered Apr 9 at 4:12

mathpadawanmathpadawan

2,087522

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes please write the full solution as well @mathpadawan Thank you very much
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 4:17
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The two degree two vertices are connected in the graph @mathpadawan I checked now. What if I add another edge between those two vertices (then it will be a multigraph with each vertex having degree 3, right?). Then also can I apply Peterson theorem? The graph is bridgeless, from the diagram I can see, but I am glad if an approach can be suggested to prove that it is bridgeless
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 8:37
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  please help me in this question. Thanks a lot in advance :)
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 8:38
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Oh! I think I got it: say the edge connecting the two degree 2 vertices is uv. subdivide uv into uwv and then add new vertex s and add edge sw, su,sv. Now apply Peterson on the resulting graph where we remove sw! How is that?
  $endgroup$
  – mathpadawan
  Apr 10 at 0:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Somebody please comments, See if the proof is correct!!!!!!!!!!!
  $endgroup$
  – mathpadawan
  Apr 10 at 1:01
  

  
  
  
  

 | 
show 3 more comments

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3170373%2fquestion-regarding-perfect-matchings-in-a-graph%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

If the two degree 2 vertices are not connected, connect them by an edge and apply Peterson's theorem and use the fact that you can pick any edge and there will be a perfect matching without that edge. Else, say the edge connecting them is $uv$, subdivide it and add a new vertex $S$ as in the following picture. So apply Peterson on the resulting graph with $SW$ removed!?

share|cite|improve this answer

edited Apr 10 at 0:59

answered Apr 9 at 4:12

mathpadawanmathpadawan

2,087522

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes please write the full solution as well @mathpadawan Thank you very much
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 4:17
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The two degree two vertices are connected in the graph @mathpadawan I checked now. What if I add another edge between those two vertices (then it will be a multigraph with each vertex having degree 3, right?). Then also can I apply Peterson theorem? The graph is bridgeless, from the diagram I can see, but I am glad if an approach can be suggested to prove that it is bridgeless
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 8:37
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  please help me in this question. Thanks a lot in advance :)
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 8:38
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Oh! I think I got it: say the edge connecting the two degree 2 vertices is uv. subdivide uv into uwv and then add new vertex s and add edge sw, su,sv. Now apply Peterson on the resulting graph where we remove sw! How is that?
  $endgroup$
  – mathpadawan
  Apr 10 at 0:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Somebody please comments, See if the proof is correct!!!!!!!!!!!
  $endgroup$
  – mathpadawan
  Apr 10 at 1:01
  

  
  
  
  

 | 
show 3 more comments

1

$begingroup$

If the two degree 2 vertices are not connected, connect them by an edge and apply Peterson's theorem and use the fact that you can pick any edge and there will be a perfect matching without that edge. Else, say the edge connecting them is $uv$, subdivide it and add a new vertex $S$ as in the following picture. So apply Peterson on the resulting graph with $SW$ removed!?

share|cite|improve this answer

edited Apr 10 at 0:59

answered Apr 9 at 4:12

mathpadawanmathpadawan

2,087522

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes please write the full solution as well @mathpadawan Thank you very much
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 4:17
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The two degree two vertices are connected in the graph @mathpadawan I checked now. What if I add another edge between those two vertices (then it will be a multigraph with each vertex having degree 3, right?). Then also can I apply Peterson theorem? The graph is bridgeless, from the diagram I can see, but I am glad if an approach can be suggested to prove that it is bridgeless
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 8:37
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  please help me in this question. Thanks a lot in advance :)
  $endgroup$
  – Buddhini Angelika
  Apr 9 at 8:38
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Oh! I think I got it: say the edge connecting the two degree 2 vertices is uv. subdivide uv into uwv and then add new vertex s and add edge sw, su,sv. Now apply Peterson on the resulting graph where we remove sw! How is that?
  $endgroup$
  – mathpadawan
  Apr 10 at 0:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Somebody please comments, See if the proof is correct!!!!!!!!!!!
  $endgroup$
  – mathpadawan
  Apr 10 at 1:01
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

If the two degree 2 vertices are not connected, connect them by an edge and apply Peterson's theorem and use the fact that you can pick any edge and there will be a perfect matching without that edge. Else, say the edge connecting them is $uv$, subdivide it and add a new vertex $S$ as in the following picture. So apply Peterson on the resulting graph with $SW$ removed!?

share|cite|improve this answer

edited Apr 10 at 0:59

answered Apr 9 at 4:12

mathpadawanmathpadawan

2,087522

$endgroup$

share|cite|improve this answer

edited Apr 10 at 0:59

answered Apr 9 at 4:12

mathpadawanmathpadawan

2,087522

answered Apr 9 at 4:12

mathpadawanmathpadawan

2,087522

answered Apr 9 at 4:12

mathpadawanmathpadawan

2,087522