Deleting vertex of graph G lowers the chromatic number by one

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

I'm currently not really able to come up with a proof for this particular problem.

Let $G=(V,E)$ be a graph with the property that $∀ v ∈ V$, $χ(G−v) = χ(G)−1$. Show that $G$ is connected.

In other words: If you delete any vertex of the graph, the chromatic number will be reduced by one.

From my understanding this can only be the case in a complete graph. Since all vertices of a complete graph are connected with each other the chromatic number must be reduced by one if you delete any vertex. Which means that if I'm able to show that $G$ is a complete graph, I will have automatically proven that $G$ is connected since every complete graph is connected. I'm just not sure how to prove that $G$ is a complete graph or how to tackle this problem in general. I'm very thankful for any help I can get!

graph-theory coloring

share|cite|improve this question

edited Jul 16 at 17:11

asked Jul 16 at 16:36

Zelda_CompSci

235

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Note that odd cycle graphs also satisfy the given property...
  – Parcly Taxel
  Jul 16 at 17:02
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

I'm currently not really able to come up with a proof for this particular problem.

Let $G=(V,E)$ be a graph with the property that $∀ v ∈ V$, $χ(G−v) = χ(G)−1$. Show that $G$ is connected.

In other words: If you delete any vertex of the graph, the chromatic number will be reduced by one.

From my understanding this can only be the case in a complete graph. Since all vertices of a complete graph are connected with each other the chromatic number must be reduced by one if you delete any vertex. Which means that if I'm able to show that $G$ is a complete graph, I will have automatically proven that $G$ is connected since every complete graph is connected. I'm just not sure how to prove that $G$ is a complete graph or how to tackle this problem in general. I'm very thankful for any help I can get!

graph-theory coloring

share|cite|improve this question

edited Jul 16 at 17:11

asked Jul 16 at 16:36

Zelda_CompSci

235

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Note that odd cycle graphs also satisfy the given property...
  – Parcly Taxel
  Jul 16 at 17:02
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

I'm currently not really able to come up with a proof for this particular problem.

Let $G=(V,E)$ be a graph with the property that $∀ v ∈ V$, $χ(G−v) = χ(G)−1$. Show that $G$ is connected.

In other words: If you delete any vertex of the graph, the chromatic number will be reduced by one.

From my understanding this can only be the case in a complete graph. Since all vertices of a complete graph are connected with each other the chromatic number must be reduced by one if you delete any vertex. Which means that if I'm able to show that $G$ is a complete graph, I will have automatically proven that $G$ is connected since every complete graph is connected. I'm just not sure how to prove that $G$ is a complete graph or how to tackle this problem in general. I'm very thankful for any help I can get!

graph-theory coloring

share|cite|improve this question

edited Jul 16 at 17:11

asked Jul 16 at 16:36

Zelda_CompSci

235

I'm currently not really able to come up with a proof for this particular problem.

Let $G=(V,E)$ be a graph with the property that $∀ v ∈ V$, $χ(G−v) = χ(G)−1$. Show that $G$ is connected.

In other words: If you delete any vertex of the graph, the chromatic number will be reduced by one.

From my understanding this can only be the case in a complete graph. Since all vertices of a complete graph are connected with each other the chromatic number must be reduced by one if you delete any vertex. Which means that if I'm able to show that $G$ is a complete graph, I will have automatically proven that $G$ is connected since every complete graph is connected. I'm just not sure how to prove that $G$ is a complete graph or how to tackle this problem in general. I'm very thankful for any help I can get!

graph-theory coloring

share|cite|improve this question

edited Jul 16 at 17:11

asked Jul 16 at 16:36

Zelda_CompSci

235

share|cite|improve this question

share|cite|improve this question

edited Jul 16 at 17:11

edited Jul 16 at 17:11

edited Jul 16 at 17:11

asked Jul 16 at 16:36

Zelda_CompSci

235

asked Jul 16 at 16:36

Zelda_CompSci

235

asked Jul 16 at 16:36

Zelda_CompSci

235

235

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Note that odd cycle graphs also satisfy the given property...
  – Parcly Taxel
  Jul 16 at 17:02
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Note that odd cycle graphs also satisfy the given property...
  – Parcly Taxel
  Jul 16 at 17:02
  
  

  
  
  
  

Note that odd cycle graphs also satisfy the given property...
– Parcly Taxel
Jul 16 at 17:02

Note that odd cycle graphs also satisfy the given property...
– Parcly Taxel
Jul 16 at 17:02

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote



accepted

Suppose $G$ is disconnected. The chromatic number of such a graph is the maximum of the chromatic numbers of its components, but a vertex can only belong to one component. Thus, if the removal of any particular vertex lowers the overall chromatic number, the component that vertex belongs to must have strictly higher chromatic number than that of the other components.

Repeating this argument, subjecting the remaining components to vertex removal, yields that every component's chromatic number is strictly higher than the others', which is absurd. Therefore, $G$ is connected.

share|cite|improve this answer

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, I would've never solved this without your help.
  – Zelda_CompSci
  Jul 16 at 20:55
  

  
  
  
  

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%2f2853580%2fdeleting-vertex-of-graph-g-lowers-the-chromatic-number-by-one%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
1
down vote



accepted

Suppose $G$ is disconnected. The chromatic number of such a graph is the maximum of the chromatic numbers of its components, but a vertex can only belong to one component. Thus, if the removal of any particular vertex lowers the overall chromatic number, the component that vertex belongs to must have strictly higher chromatic number than that of the other components.

Repeating this argument, subjecting the remaining components to vertex removal, yields that every component's chromatic number is strictly higher than the others', which is absurd. Therefore, $G$ is connected.

share|cite|improve this answer

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, I would've never solved this without your help.
  – Zelda_CompSci
  Jul 16 at 20:55
  

  
  
  
  

add a comment | 

up vote
1
down vote



accepted

Suppose $G$ is disconnected. The chromatic number of such a graph is the maximum of the chromatic numbers of its components, but a vertex can only belong to one component. Thus, if the removal of any particular vertex lowers the overall chromatic number, the component that vertex belongs to must have strictly higher chromatic number than that of the other components.

Repeating this argument, subjecting the remaining components to vertex removal, yields that every component's chromatic number is strictly higher than the others', which is absurd. Therefore, $G$ is connected.

share|cite|improve this answer

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, I would've never solved this without your help.
  – Zelda_CompSci
  Jul 16 at 20:55
  

  
  
  
  

add a comment | 

up vote
1
down vote



accepted

up vote
1
down vote



accepted

Suppose $G$ is disconnected. The chromatic number of such a graph is the maximum of the chromatic numbers of its components, but a vertex can only belong to one component. Thus, if the removal of any particular vertex lowers the overall chromatic number, the component that vertex belongs to must have strictly higher chromatic number than that of the other components.

Repeating this argument, subjecting the remaining components to vertex removal, yields that every component's chromatic number is strictly higher than the others', which is absurd. Therefore, $G$ is connected.

share|cite|improve this answer

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

Suppose $G$ is disconnected. The chromatic number of such a graph is the maximum of the chromatic numbers of its components, but a vertex can only belong to one component. Thus, if the removal of any particular vertex lowers the overall chromatic number, the component that vertex belongs to must have strictly higher chromatic number than that of the other components.

Repeating this argument, subjecting the remaining components to vertex removal, yields that every component's chromatic number is strictly higher than the others', which is absurd. Therefore, $G$ is connected.

share|cite|improve this answer

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

share|cite|improve this answer

share|cite|improve this answer

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

answered Jul 16 at 17:00

Parcly Taxel

33.6k136588

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, I would've never solved this without your help.
  – Zelda_CompSci
  Jul 16 at 20:55
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, I would've never solved this without your help.
  – Zelda_CompSci
  Jul 16 at 20:55
  

  
  
  
  

Thanks, I would've never solved this without your help.
– Zelda_CompSci
Jul 16 at 20:55

Thanks, I would've never solved this without your help.
– Zelda_CompSci
Jul 16 at 20:55

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%2f2853580%2fdeleting-vertex-of-graph-g-lowers-the-chromatic-number-by-one%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