Fdtxjr

Define, (actually define) the "stability" and "energy" of a compound

What approach do we need to follow for projects without a test environment?

Who is flying the vertibirds?

Python if-else code style for reduced code for rounding floats

Have researchers managed to "reverse time"? If so, what does that mean for physics?

How to create the Curved texte?

How to deal with taxi scam when on vacation?

Why does Bach not break the rules here?

How big is a MODIS 250m pixel in reality?

Welcoming 2019 Pi day: How to draw the letter π?

If curse and magic is two sides of the same coin, why the former is forbidden?

Instead of Universal Basic Income, why not Universal Basic NEEDS?

Use of undefined constant bloginfo

how to draw discrete time diagram in tikz

Does Mathematica reuse previous computations?

What exactly is this small puffer fish doing and how did it manage to accomplish such a feat?

Min function accepting varying number of arguments in C++17

How to deal with a cynical class?

How to change two letters closest to a string and one letter immediately after a string using notepad++

Is there a data structure that only stores hash codes and not the actual objects?

Happy pi day, everyone!

How to explain that I do not want to visit a country due to personal safety concern?

How to make healing in an exploration game interesting

What did Alexander Pope mean by "Expletives their feeble Aid do join"?

Chromatic polynomial properties

Proof that the chromatic polynomial of a simple graph G with n vertices has degree n.Chromatic polynomial of a simple disconnected graphplanar graph and chromatic numberGraphs which satisfy $chi(G) > chi(H)$ and $p_G(x) > p_H(x)$?Find out chromatic number of graph if $deg(G) leq 3$.Chromatic Number and Chromatic Polynomial of a GraphWhy is the constant term in any chromatic polynomial is always zero?Finding the Chromatic Polynomial for the wheel graph $W_5$Some (trivial?) doubts on the proof of chromatic number of any planar graph is at most 6Relation between vertex chromatic number and vertex connectivity.Coloring of graphs — Chromatic number and inductionGraphs theory chromatic polynomial

1

1

$begingroup$

I have some properties which I do not understand how to form a proof for.
Most of them are by induction, which is not my strong point
Any help would be fantastic.

Looking at the chromatic polynomial $$P_G(k)=P_G-e(k) - P_G/e(k)$$

Properties

1.If G has n vertices then $ P_g(k)$ has degree n and the coefficient of $k^n $ is 1

2. The signs of $P_g(k) $ alternate




3. If G has q components the smalles non-zero term of $P_g(k)$ is the term in $k^q$

linear-algebra graph-theory

share|cite|improve this question

edited Jan 16 at 17:41

Thomas Lesgourgues

1,126119

asked Jan 16 at 17:12

p sp s

428

$endgroup$

add a comment | 

1

1

$begingroup$

I have some properties which I do not understand how to form a proof for.
Most of them are by induction, which is not my strong point
Any help would be fantastic.

Looking at the chromatic polynomial $$P_G(k)=P_G-e(k) - P_G/e(k)$$

Properties

1.If G has n vertices then $ P_g(k)$ has degree n and the coefficient of $k^n $ is 1

2. The signs of $P_g(k) $ alternate




3. If G has q components the smalles non-zero term of $P_g(k)$ is the term in $k^q$

linear-algebra graph-theory

share|cite|improve this question

edited Jan 16 at 17:41

Thomas Lesgourgues

1,126119

asked Jan 16 at 17:12

p sp s

428

$endgroup$

add a comment | 

$begingroup$

I have some properties which I do not understand how to form a proof for.
Most of them are by induction, which is not my strong point
Any help would be fantastic.

Looking at the chromatic polynomial $$P_G(k)=P_G-e(k) - P_G/e(k)$$

Properties

1.If G has n vertices then $ P_g(k)$ has degree n and the coefficient of $k^n $ is 1

2. The signs of $P_g(k) $ alternate




3. If G has q components the smalles non-zero term of $P_g(k)$ is the term in $k^q$

linear-algebra graph-theory

share|cite|improve this question

edited Jan 16 at 17:41

Thomas Lesgourgues

1,126119

asked Jan 16 at 17:12

p sp s

428

$endgroup$

share|cite|improve this question

edited Jan 16 at 17:41

Thomas Lesgourgues

1,126119

asked Jan 16 at 17:12

p sp s

428

share|cite|improve this question

edited Jan 16 at 17:41

Thomas Lesgourgues

1,126119

asked Jan 16 at 17:12

p sp s

428

edited Jan 16 at 17:41

Thomas Lesgourgues

1,126119

edited Jan 16 at 17:41

Thomas Lesgourgues

1,126119

asked Jan 16 at 17:12

p sp s

428

asked Jan 16 at 17:12

p sp s

428

1 Answer
1

active

oldest

votes

1

$begingroup$

The proof works by strong induction on $m=|E(G)|$. We also prove that the coefficient of $k^n-1$ is $m$ the number of edges.

Base case : $m=0$. Then $G$ is $n$ isolated vertices. And clearly $P_G(k) = k^n$. Satisfying all results

Induction : Suppose the hypothesis are true for all graphs with at most $m$ edges. Let $G$ be a graph on $m+1$ edegs, $n$ vertices, $q$ components, and let $e in E(G)$. Then

• 
  $G-e$ has $m$ edges, $n$ vertices, $q$ or $q+1$ components


• 
  $G/e$ has at most $m$ edges, with $n-1$ vertices, and $q$ components.

Using the induction hypothesis :
beginalign
P_G-e(k) = k^n - m &k^n-1 + ldots - ldots pm bk^q \
P_G/e(k) = &k^n-1 - ldots + ldots mp ck^q
endalign
With $bgeq 0$ and $c>0$. Therefore
$$ P_G(k) = k^n - (m+1) k^n + ldots - ldots + ldots pm (b+c)k^q$$
With $b+c >0$. Provind that $P_G(k)$ is monic, with alternating signs, with second coefficient $m+1$ its number of edges, and smallest coefficient the number $q$ of components.

share|cite|improve this answer

answered Jan 17 at 12:27

Thomas LesgourguesThomas Lesgourgues

1,126119

$endgroup$

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%2f3075993%2fchromatic-polynomial-properties%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

The proof works by strong induction on $m=|E(G)|$. We also prove that the coefficient of $k^n-1$ is $m$ the number of edges.

Base case : $m=0$. Then $G$ is $n$ isolated vertices. And clearly $P_G(k) = k^n$. Satisfying all results

Induction : Suppose the hypothesis are true for all graphs with at most $m$ edges. Let $G$ be a graph on $m+1$ edegs, $n$ vertices, $q$ components, and let $e in E(G)$. Then

• 
  $G-e$ has $m$ edges, $n$ vertices, $q$ or $q+1$ components


• 
  $G/e$ has at most $m$ edges, with $n-1$ vertices, and $q$ components.

Using the induction hypothesis :
beginalign
P_G-e(k) = k^n - m &k^n-1 + ldots - ldots pm bk^q \
P_G/e(k) = &k^n-1 - ldots + ldots mp ck^q
endalign
With $bgeq 0$ and $c>0$. Therefore
$$ P_G(k) = k^n - (m+1) k^n + ldots - ldots + ldots pm (b+c)k^q$$
With $b+c >0$. Provind that $P_G(k)$ is monic, with alternating signs, with second coefficient $m+1$ its number of edges, and smallest coefficient the number $q$ of components.

share|cite|improve this answer

answered Jan 17 at 12:27

Thomas LesgourguesThomas Lesgourgues

1,126119

$endgroup$

add a comment | 

1

$begingroup$

The proof works by strong induction on $m=|E(G)|$. We also prove that the coefficient of $k^n-1$ is $m$ the number of edges.

Base case : $m=0$. Then $G$ is $n$ isolated vertices. And clearly $P_G(k) = k^n$. Satisfying all results

Induction : Suppose the hypothesis are true for all graphs with at most $m$ edges. Let $G$ be a graph on $m+1$ edegs, $n$ vertices, $q$ components, and let $e in E(G)$. Then

• 
  $G-e$ has $m$ edges, $n$ vertices, $q$ or $q+1$ components


• 
  $G/e$ has at most $m$ edges, with $n-1$ vertices, and $q$ components.

Using the induction hypothesis :
beginalign
P_G-e(k) = k^n - m &k^n-1 + ldots - ldots pm bk^q \
P_G/e(k) = &k^n-1 - ldots + ldots mp ck^q
endalign
With $bgeq 0$ and $c>0$. Therefore
$$ P_G(k) = k^n - (m+1) k^n + ldots - ldots + ldots pm (b+c)k^q$$
With $b+c >0$. Provind that $P_G(k)$ is monic, with alternating signs, with second coefficient $m+1$ its number of edges, and smallest coefficient the number $q$ of components.

share|cite|improve this answer

answered Jan 17 at 12:27

Thomas LesgourguesThomas Lesgourgues

1,126119

$endgroup$

add a comment | 

$begingroup$

The proof works by strong induction on $m=|E(G)|$. We also prove that the coefficient of $k^n-1$ is $m$ the number of edges.

Base case : $m=0$. Then $G$ is $n$ isolated vertices. And clearly $P_G(k) = k^n$. Satisfying all results

Induction : Suppose the hypothesis are true for all graphs with at most $m$ edges. Let $G$ be a graph on $m+1$ edegs, $n$ vertices, $q$ components, and let $e in E(G)$. Then

• 
  $G-e$ has $m$ edges, $n$ vertices, $q$ or $q+1$ components


• 
  $G/e$ has at most $m$ edges, with $n-1$ vertices, and $q$ components.

Using the induction hypothesis :
beginalign
P_G-e(k) = k^n - m &k^n-1 + ldots - ldots pm bk^q \
P_G/e(k) = &k^n-1 - ldots + ldots mp ck^q
endalign
With $bgeq 0$ and $c>0$. Therefore
$$ P_G(k) = k^n - (m+1) k^n + ldots - ldots + ldots pm (b+c)k^q$$
With $b+c >0$. Provind that $P_G(k)$ is monic, with alternating signs, with second coefficient $m+1$ its number of edges, and smallest coefficient the number $q$ of components.

share|cite|improve this answer

answered Jan 17 at 12:27

Thomas LesgourguesThomas Lesgourgues

1,126119

$endgroup$

share|cite|improve this answer

answered Jan 17 at 12:27

Thomas LesgourguesThomas Lesgourgues

1,126119

answered Jan 17 at 12:27

Thomas LesgourguesThomas Lesgourgues

1,126119

answered Jan 17 at 12:27

Thomas LesgourguesThomas Lesgourgues

1,126119