Fdtxjr

Is there a hemisphere-neutral way of specifying a season?

One verb to replace 'be a member of' a club

How could indestructible materials be used in power generation?

What about the virus in 12 Monkeys?

Do UK voters know if their MP will be the Speaker of the House?

Mathematica command that allows it to read my intentions

I would say: "You are another teacher", but she is a woman and I am a man

Can a virus destroy the BIOS of a modern computer?

Avoiding the "not like other girls" trope?

How do conventional missiles fly?

Is there an expression that means doing something right before you will need it rather than doing it in case you might need it?

How can saying a song's name be a copyright violation?

Gatling : Performance testing tool

Intersection Puzzle

What does “the session was packed” mean in this context?

How to tell a function to use the default argument values?

Ambiguity in the definition of entropy

How do I gain back my faith in my PhD degree?

Would Slavery Reparations be considered Bills of Attainder and hence Illegal?

What exploit are these user agents trying to use?

What reasons are there for a Capitalist to oppose a 100% inheritance tax?

Are there any examples of a variable being normally distributed that is *not* due to the Central Limit Theorem?

If human space travel is limited by the G force vulnerability, is there a way to counter G forces?

Is it possible to create a QR code using text?

Each node has three edges, proof that we can make 4 pairs of nodes which are not connected

A lower bound on the number of edges in a graph satisfying a “subset matching” propertyHow many weakly-connected digraphs of n vertices are there without loops and whose vertices all have indegree 1?n-degree neighborhood of a node vGraph Theory Proof - Hamilton Decomposition of 4-regular GraphsHow to pick $N$ “special” nodes in connected graph $G$ so that average distance from any non-special node to nearest special node is minimized?How to create a dense graph, when each node has a limited number of edges?Graph Puzzle with labelsAlgorithm that can divide all graph nodes N into two fully connected sets?Number of tagged trees $T=(V,E)$ on $10$ vertices such that $deg(v_i)=i$ for $1 le i le 3$What is the probability that a graph containing n nodes with k random edges each will be strongly connected?

2

$begingroup$

Question. Graph $G$ has 8 nodes, each node has 3 edges. Proof that it is able to split the nodes into 4 pairs which is not connected each other.

For example, we can divide it like the picture shown below.

My approach.

I can solve this problem by dividing the possible cases into four.

When I set the nodes $V_1, V_2, cdots, V_8$, WLOG Let $V_1$ and $V_2, V_3, V_4$ connected each other.

We can divide the cases into four, which is:

1. 
   $V_2, V_3, V_4$ is all connected each other (So, there are three pairs connected each other)


2. Only two pairs of $V_2, V_3, V_4$ is connected each other


3. Only one pair of $V_2, V_3, V_4$ is connected each other


4. No pairs of $V_2, V_3, V_4$ is connected each other

The problem is, I think I can solve this problem in this way, but I think there is a better way.

What should it be?

graph-theory

share|cite|improve this question

edited Mar 21 at 8:32

coding1101

asked Mar 21 at 8:23

coding1101coding1101

1246

$endgroup$

add a comment | 

2

$begingroup$

Question. Graph $G$ has 8 nodes, each node has 3 edges. Proof that it is able to split the nodes into 4 pairs which is not connected each other.

For example, we can divide it like the picture shown below.

My approach.

I can solve this problem by dividing the possible cases into four.

When I set the nodes $V_1, V_2, cdots, V_8$, WLOG Let $V_1$ and $V_2, V_3, V_4$ connected each other.

We can divide the cases into four, which is:

1. 
   $V_2, V_3, V_4$ is all connected each other (So, there are three pairs connected each other)


2. Only two pairs of $V_2, V_3, V_4$ is connected each other


3. Only one pair of $V_2, V_3, V_4$ is connected each other


4. No pairs of $V_2, V_3, V_4$ is connected each other

The problem is, I think I can solve this problem in this way, but I think there is a better way.

What should it be?

graph-theory

share|cite|improve this question

edited Mar 21 at 8:32

coding1101

asked Mar 21 at 8:23

coding1101coding1101

1246

$endgroup$

add a comment | 

$begingroup$

Question. Graph $G$ has 8 nodes, each node has 3 edges. Proof that it is able to split the nodes into 4 pairs which is not connected each other.

For example, we can divide it like the picture shown below.

My approach.

I can solve this problem by dividing the possible cases into four.

When I set the nodes $V_1, V_2, cdots, V_8$, WLOG Let $V_1$ and $V_2, V_3, V_4$ connected each other.

We can divide the cases into four, which is:

1. 
   $V_2, V_3, V_4$ is all connected each other (So, there are three pairs connected each other)


2. Only two pairs of $V_2, V_3, V_4$ is connected each other


3. Only one pair of $V_2, V_3, V_4$ is connected each other


4. No pairs of $V_2, V_3, V_4$ is connected each other

The problem is, I think I can solve this problem in this way, but I think there is a better way.

What should it be?

graph-theory

share|cite|improve this question

edited Mar 21 at 8:32

coding1101

asked Mar 21 at 8:23

coding1101coding1101

1246

$endgroup$

share|cite|improve this question

edited Mar 21 at 8:32

coding1101

asked Mar 21 at 8:23

coding1101coding1101

1246

share|cite|improve this question

edited Mar 21 at 8:32

coding1101

asked Mar 21 at 8:23

coding1101coding1101

1246

asked Mar 21 at 8:23

coding1101coding1101

1246

asked Mar 21 at 8:23

coding1101coding1101

1246

1 Answer
1

active

oldest

votes

1

$begingroup$

Hint

Your computation will work but it is indeed a bit tedious, and would quickly be not feasible with higher number of nodes. If you want to do something "neat":

Call $G=(V,E)$ your graph, on 8 nodes, 3-regular, hence on 12 edges. Note that your problem is equivalent to

Find a perfect matching in the complement of $G$

Indeed If you find a perfect matching in $G^c$ (the complement of $G$), then you will have a way to pair all nodes, with no edges (in $G$) between elements of a pair.
Now your graph $G^c$ has 8 nodes, and is 4-regular. Do you have notions of perfect matching? and how to prove they exist?

To finish you could

Say that you have a 4-regular graph with $n=8$ nodes, hence the graph must be connected. Hence the graph includes an eulerian cycle. Select every other edges in this cycle and you end up with a 2 factors, made up of collection of even cycle. select every second edges in these cycles and you obtain the desired perfect matching.

share|cite|improve this answer

edited Mar 21 at 9:29

answered Mar 21 at 9:01

Thomas LesgourguesThomas Lesgourgues

1,283220

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Isn't the eulerian cycle the cycle which contains all the edges in the graph? What does "every other edges in this cycle" mean?
  $endgroup$
  – coding1101
  Mar 21 at 9:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think I can prove it like this. Graph G^C is a connected graph, so graph $G^C$ includes a hamilton cycle. (Because the degrees is all $4 ge fracn2$) So there is a perfect matching.
  $endgroup$
  – coding1101
  Mar 21 at 9:51
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  yep, for $n=8$ you can conclude like that. For information "every other edges", or "every second edges" means the same, taking half the edges : Yes,no,yes,no,...
  $endgroup$
  – Thomas Lesgourgues
  Mar 21 at 14:17
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

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%2f3156516%2feach-node-has-three-edges-proof-that-we-can-make-4-pairs-of-nodes-which-are-not%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Hint

Your computation will work but it is indeed a bit tedious, and would quickly be not feasible with higher number of nodes. If you want to do something "neat":

Call $G=(V,E)$ your graph, on 8 nodes, 3-regular, hence on 12 edges. Note that your problem is equivalent to

Find a perfect matching in the complement of $G$

Indeed If you find a perfect matching in $G^c$ (the complement of $G$), then you will have a way to pair all nodes, with no edges (in $G$) between elements of a pair.
Now your graph $G^c$ has 8 nodes, and is 4-regular. Do you have notions of perfect matching? and how to prove they exist?

To finish you could

Say that you have a 4-regular graph with $n=8$ nodes, hence the graph must be connected. Hence the graph includes an eulerian cycle. Select every other edges in this cycle and you end up with a 2 factors, made up of collection of even cycle. select every second edges in these cycles and you obtain the desired perfect matching.

share|cite|improve this answer

edited Mar 21 at 9:29

answered Mar 21 at 9:01

Thomas LesgourguesThomas Lesgourgues

1,283220

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Isn't the eulerian cycle the cycle which contains all the edges in the graph? What does "every other edges in this cycle" mean?
  $endgroup$
  – coding1101
  Mar 21 at 9:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think I can prove it like this. Graph G^C is a connected graph, so graph $G^C$ includes a hamilton cycle. (Because the degrees is all $4 ge fracn2$) So there is a perfect matching.
  $endgroup$
  – coding1101
  Mar 21 at 9:51
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  yep, for $n=8$ you can conclude like that. For information "every other edges", or "every second edges" means the same, taking half the edges : Yes,no,yes,no,...
  $endgroup$
  – Thomas Lesgourgues
  Mar 21 at 14:17
  

  
  
  
  

add a comment | 

1

$begingroup$

Hint

Your computation will work but it is indeed a bit tedious, and would quickly be not feasible with higher number of nodes. If you want to do something "neat":

Call $G=(V,E)$ your graph, on 8 nodes, 3-regular, hence on 12 edges. Note that your problem is equivalent to

Find a perfect matching in the complement of $G$

Indeed If you find a perfect matching in $G^c$ (the complement of $G$), then you will have a way to pair all nodes, with no edges (in $G$) between elements of a pair.
Now your graph $G^c$ has 8 nodes, and is 4-regular. Do you have notions of perfect matching? and how to prove they exist?

To finish you could

Say that you have a 4-regular graph with $n=8$ nodes, hence the graph must be connected. Hence the graph includes an eulerian cycle. Select every other edges in this cycle and you end up with a 2 factors, made up of collection of even cycle. select every second edges in these cycles and you obtain the desired perfect matching.

share|cite|improve this answer

edited Mar 21 at 9:29

answered Mar 21 at 9:01

Thomas LesgourguesThomas Lesgourgues

1,283220

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Isn't the eulerian cycle the cycle which contains all the edges in the graph? What does "every other edges in this cycle" mean?
  $endgroup$
  – coding1101
  Mar 21 at 9:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think I can prove it like this. Graph G^C is a connected graph, so graph $G^C$ includes a hamilton cycle. (Because the degrees is all $4 ge fracn2$) So there is a perfect matching.
  $endgroup$
  – coding1101
  Mar 21 at 9:51
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  yep, for $n=8$ you can conclude like that. For information "every other edges", or "every second edges" means the same, taking half the edges : Yes,no,yes,no,...
  $endgroup$
  – Thomas Lesgourgues
  Mar 21 at 14:17
  

  
  
  
  

add a comment | 

$begingroup$

Hint

Your computation will work but it is indeed a bit tedious, and would quickly be not feasible with higher number of nodes. If you want to do something "neat":

Call $G=(V,E)$ your graph, on 8 nodes, 3-regular, hence on 12 edges. Note that your problem is equivalent to

Find a perfect matching in the complement of $G$

Indeed If you find a perfect matching in $G^c$ (the complement of $G$), then you will have a way to pair all nodes, with no edges (in $G$) between elements of a pair.
Now your graph $G^c$ has 8 nodes, and is 4-regular. Do you have notions of perfect matching? and how to prove they exist?

To finish you could

Say that you have a 4-regular graph with $n=8$ nodes, hence the graph must be connected. Hence the graph includes an eulerian cycle. Select every other edges in this cycle and you end up with a 2 factors, made up of collection of even cycle. select every second edges in these cycles and you obtain the desired perfect matching.

share|cite|improve this answer

edited Mar 21 at 9:29

answered Mar 21 at 9:01

Thomas LesgourguesThomas Lesgourgues

1,283220

$endgroup$

share|cite|improve this answer

edited Mar 21 at 9:29

answered Mar 21 at 9:01

Thomas LesgourguesThomas Lesgourgues

1,283220

answered Mar 21 at 9:01

Thomas LesgourguesThomas Lesgourgues

1,283220

answered Mar 21 at 9:01

Thomas LesgourguesThomas Lesgourgues

1,283220