Degree Sequence Problem

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

I found this degree sequencing problem interesting and tried to work it out but got stuck. I would like to find the graphs with the following degree sequence:

For $ N>4 $, the degree sequence of a set of graphs is defined as follows:

$ (N, N, N, N, 4, 4, 4, ... ) $,

where the number of $ 4's $ in the degree sequence is equal to $ (N-2)^2 $.

For each $ N $ prove that there are at least two graphs with the given degree sequence.

Prove that for each $ N $ there is only one planar graph that satisfies the degree sequence.

If there is only one planar graph that satisfies the degree sequence is that interesting or uninteresting?

graph-theory

share|cite|improve this question

edited Jul 18 at 21:12

asked Jul 17 at 22:37

George Thomas

33416

add a comment | 

up vote
2
down vote

favorite

I found this degree sequencing problem interesting and tried to work it out but got stuck. I would like to find the graphs with the following degree sequence:

For $ N>4 $, the degree sequence of a set of graphs is defined as follows:

$ (N, N, N, N, 4, 4, 4, ... ) $,

where the number of $ 4's $ in the degree sequence is equal to $ (N-2)^2 $.

For each $ N $ prove that there are at least two graphs with the given degree sequence.

Prove that for each $ N $ there is only one planar graph that satisfies the degree sequence.

If there is only one planar graph that satisfies the degree sequence is that interesting or uninteresting?

graph-theory

share|cite|improve this question

edited Jul 18 at 21:12

asked Jul 17 at 22:37

George Thomas

33416

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

I found this degree sequencing problem interesting and tried to work it out but got stuck. I would like to find the graphs with the following degree sequence:

For $ N>4 $, the degree sequence of a set of graphs is defined as follows:

$ (N, N, N, N, 4, 4, 4, ... ) $,

where the number of $ 4's $ in the degree sequence is equal to $ (N-2)^2 $.

For each $ N $ prove that there are at least two graphs with the given degree sequence.

Prove that for each $ N $ there is only one planar graph that satisfies the degree sequence.

If there is only one planar graph that satisfies the degree sequence is that interesting or uninteresting?

graph-theory

share|cite|improve this question

edited Jul 18 at 21:12

asked Jul 17 at 22:37

George Thomas

33416

I found this degree sequencing problem interesting and tried to work it out but got stuck. I would like to find the graphs with the following degree sequence:

For $ N>4 $, the degree sequence of a set of graphs is defined as follows:

$ (N, N, N, N, 4, 4, 4, ... ) $,

where the number of $ 4's $ in the degree sequence is equal to $ (N-2)^2 $.

For each $ N $ prove that there are at least two graphs with the given degree sequence.

Prove that for each $ N $ there is only one planar graph that satisfies the degree sequence.

If there is only one planar graph that satisfies the degree sequence is that interesting or uninteresting?

graph-theory

share|cite|improve this question

edited Jul 18 at 21:12

asked Jul 17 at 22:37

George Thomas

33416

share|cite|improve this question

share|cite|improve this question

edited Jul 18 at 21:12

edited Jul 18 at 21:12

edited Jul 18 at 21:12

asked Jul 17 at 22:37

George Thomas

33416

asked Jul 17 at 22:37

George Thomas

33416

asked Jul 17 at 22:37

George Thomas

33416

33416

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
3
down vote



accepted

+50

For $N=5$ the degree sequence is $(colorblue5^4, colorred4^9)$ (where multiplicities have been indicated by using exponents. The obvious planar graph with this degree is

BUT this is not the only planar graph with this degree sequence !

share|cite|improve this answer

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  A small addition to this answer: It is easy to see these graphs are not isomorphic by looking at the number of red nodes with four red neighbours, or by looking at the number of blue nodes with two blue neighbours.
  – B. Mehta
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there anything interesting about the number of planar representations for a degree sequence?
  – George Thomas
  Jul 20 at 18:53
  

  
  
  
  

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854997%2fdegree-sequence-problem%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
3
down vote



accepted

+50

For $N=5$ the degree sequence is $(colorblue5^4, colorred4^9)$ (where multiplicities have been indicated by using exponents. The obvious planar graph with this degree is

BUT this is not the only planar graph with this degree sequence !

share|cite|improve this answer

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  A small addition to this answer: It is easy to see these graphs are not isomorphic by looking at the number of red nodes with four red neighbours, or by looking at the number of blue nodes with two blue neighbours.
  – B. Mehta
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there anything interesting about the number of planar representations for a degree sequence?
  – George Thomas
  Jul 20 at 18:53
  

  
  
  
  

add a comment | 

up vote
3
down vote



accepted

+50

For $N=5$ the degree sequence is $(colorblue5^4, colorred4^9)$ (where multiplicities have been indicated by using exponents. The obvious planar graph with this degree is

BUT this is not the only planar graph with this degree sequence !

share|cite|improve this answer

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  A small addition to this answer: It is easy to see these graphs are not isomorphic by looking at the number of red nodes with four red neighbours, or by looking at the number of blue nodes with two blue neighbours.
  – B. Mehta
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there anything interesting about the number of planar representations for a degree sequence?
  – George Thomas
  Jul 20 at 18:53
  

  
  
  
  

add a comment | 

up vote
3
down vote



accepted

+50

up vote
3
down vote



accepted

+50

+50

For $N=5$ the degree sequence is $(colorblue5^4, colorred4^9)$ (where multiplicities have been indicated by using exponents. The obvious planar graph with this degree is

BUT this is not the only planar graph with this degree sequence !

share|cite|improve this answer

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

For $N=5$ the degree sequence is $(colorblue5^4, colorred4^9)$ (where multiplicities have been indicated by using exponents. The obvious planar graph with this degree is

BUT this is not the only planar graph with this degree sequence !

share|cite|improve this answer

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

share|cite|improve this answer

share|cite|improve this answer

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

answered Jul 20 at 0:35

Donald Splutterwit

21.3k21243

21.3k21243

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  A small addition to this answer: It is easy to see these graphs are not isomorphic by looking at the number of red nodes with four red neighbours, or by looking at the number of blue nodes with two blue neighbours.
  – B. Mehta
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there anything interesting about the number of planar representations for a degree sequence?
  – George Thomas
  Jul 20 at 18:53
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  A small addition to this answer: It is easy to see these graphs are not isomorphic by looking at the number of red nodes with four red neighbours, or by looking at the number of blue nodes with two blue neighbours.
  – B. Mehta
  Jul 20 at 0:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there anything interesting about the number of planar representations for a degree sequence?
  – George Thomas
  Jul 20 at 18:53
  

  
  
  
  

1

1

A small addition to this answer: It is easy to see these graphs are not isomorphic by looking at the number of red nodes with four red neighbours, or by looking at the number of blue nodes with two blue neighbours.
– B. Mehta
Jul 20 at 0:39

A small addition to this answer: It is easy to see these graphs are not isomorphic by looking at the number of red nodes with four red neighbours, or by looking at the number of blue nodes with two blue neighbours.
– B. Mehta
Jul 20 at 0:39

Is there anything interesting about the number of planar representations for a degree sequence?
– George Thomas
Jul 20 at 18:53

Is there anything interesting about the number of planar representations for a degree sequence?
– George Thomas
Jul 20 at 18:53

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854997%2fdegree-sequence-problem%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email