If the deletion G-v is regular then G either the complete graph or its complement Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)A connected k-regular bipartite graph is 2-connected.Prove complement of this 12-vertex graph is a treeInduced subgraphs of a complete graph.Breaking connectedness by removing edges from the complete graph $K_n$11-vertex graph with nonplanar complementIf the diameter of graph is greater than 3 then the diameter of its complement graph is less than 3Complement of undirected graphTriangle-free Graph is RegularComplement of k regular graphHow to show that complement a of regular graph is a Hamiltonian graph?
Is there a service that would inform me whenever a new direct route is scheduled from a given airport?
What does '1 unit of lemon juice' mean in a grandma's drink recipe?
Is high blood pressure ever a symptom attributable solely to dehydration?
Stars Make Stars
What happens to sewage if there is no river near by?
Why did the IBM 650 use bi-quinary?
Antler Helmet: Can it work?
Bonus calculation: Am I making a mountain out of a molehill?
When to stop saving and start investing?
Is there a documented rationale why the House Ways and Means chairman can demand tax info?
Gastric acid as a weapon
Is it true that "carbohydrates are of no use for the basal metabolic need"?
ListPlot join points by nearest neighbor rather than order
What would be the ideal power source for a cybernetic eye?
How to deal with a team lead who never gives me credit?
How to motivate offshore teams and trust them to deliver?
Is it possible to boil a liquid by just mixing many immiscible liquids together?
IndentationError when pasting code in Python 3 interpreter mode
Why there are no cargo aircraft with "flying wing" design?
Are variable time comparisons always a security risk in cryptography code?
Right-skewed distribution with mean equals to mode?
Why is black pepper both grey and black?
Precipitating silver(I) salts from the solution of barium(II) cyanate and iodide
Should I call the interviewer directly, if HR aren't responding?
If the deletion G-v is regular then G either the complete graph or its complement
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)A connected k-regular bipartite graph is 2-connected.Prove complement of this 12-vertex graph is a treeInduced subgraphs of a complete graph.Breaking connectedness by removing edges from the complete graph $K_n$11-vertex graph with nonplanar complementIf the diameter of graph is greater than 3 then the diameter of its complement graph is less than 3Complement of undirected graphTriangle-free Graph is RegularComplement of k regular graphHow to show that complement a of regular graph is a Hamiltonian graph?
$begingroup$
Assume that G is a simple graph of order n, with n ≥ 4, and that for each vertex v of G,
the deletion G − v is regular (that is, all vertices have the same degree). Prove that G is
either the complete graph K_n or its complement.
This seems conceptually obvious, but i am struggling with how to form a proof.
Say the degree of each vertex in G-v is k, then the degree of v must be k+1 as it connects to each vertex in G-v. So when v is deleted it decreases the degree of adjacent vertices by one. This means that G is k+1 regular. But how do I prove that this is the complete graph or its complement?
graph-theory
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
$endgroup$
add a comment |
$begingroup$
Assume that G is a simple graph of order n, with n ≥ 4, and that for each vertex v of G,
the deletion G − v is regular (that is, all vertices have the same degree). Prove that G is
either the complete graph K_n or its complement.
This seems conceptually obvious, but i am struggling with how to form a proof.
Say the degree of each vertex in G-v is k, then the degree of v must be k+1 as it connects to each vertex in G-v. So when v is deleted it decreases the degree of adjacent vertices by one. This means that G is k+1 regular. But how do I prove that this is the complete graph or its complement?
graph-theory
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
$endgroup$
add a comment |
$begingroup$
Assume that G is a simple graph of order n, with n ≥ 4, and that for each vertex v of G,
the deletion G − v is regular (that is, all vertices have the same degree). Prove that G is
either the complete graph K_n or its complement.
This seems conceptually obvious, but i am struggling with how to form a proof.
Say the degree of each vertex in G-v is k, then the degree of v must be k+1 as it connects to each vertex in G-v. So when v is deleted it decreases the degree of adjacent vertices by one. This means that G is k+1 regular. But how do I prove that this is the complete graph or its complement?
graph-theory
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
$endgroup$
Assume that G is a simple graph of order n, with n ≥ 4, and that for each vertex v of G,
the deletion G − v is regular (that is, all vertices have the same degree). Prove that G is
either the complete graph K_n or its complement.
This seems conceptually obvious, but i am struggling with how to form a proof.
Say the degree of each vertex in G-v is k, then the degree of v must be k+1 as it connects to each vertex in G-v. So when v is deleted it decreases the degree of adjacent vertices by one. This means that G is k+1 regular. But how do I prove that this is the complete graph or its complement?
graph-theory
graph-theory
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
asked Mar 31 at 22:55
Rebecca WilliamsRebecca Williams
82
82
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Obviously, G is regular. Denote the common degree in G by d. Claim that d is either n-1(n is the number of vertices of G) or 0, otherwise by deleting any vertex v, since some vertices are adjacent to v and others are not, these two group of vertices in G-v has different degrees, one is d and the other one is d-1. That’s a contradiction.
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
$endgroup$
add a comment |
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
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3169988%2fif-the-deletion-g-v-is-regular-then-g-either-the-complete-graph-or-its-complemen%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Obviously, G is regular. Denote the common degree in G by d. Claim that d is either n-1(n is the number of vertices of G) or 0, otherwise by deleting any vertex v, since some vertices are adjacent to v and others are not, these two group of vertices in G-v has different degrees, one is d and the other one is d-1. That’s a contradiction.
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
$endgroup$
add a comment |
$begingroup$
Obviously, G is regular. Denote the common degree in G by d. Claim that d is either n-1(n is the number of vertices of G) or 0, otherwise by deleting any vertex v, since some vertices are adjacent to v and others are not, these two group of vertices in G-v has different degrees, one is d and the other one is d-1. That’s a contradiction.
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
$endgroup$
add a comment |
$begingroup$
Obviously, G is regular. Denote the common degree in G by d. Claim that d is either n-1(n is the number of vertices of G) or 0, otherwise by deleting any vertex v, since some vertices are adjacent to v and others are not, these two group of vertices in G-v has different degrees, one is d and the other one is d-1. That’s a contradiction.
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
$endgroup$
Obviously, G is regular. Denote the common degree in G by d. Claim that d is either n-1(n is the number of vertices of G) or 0, otherwise by deleting any vertex v, since some vertices are adjacent to v and others are not, these two group of vertices in G-v has different degrees, one is d and the other one is d-1. That’s a contradiction.
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
answered Apr 2 at 8:23
Yixuan HuangYixuan Huang
214
214
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3169988%2fif-the-deletion-g-v-is-regular-then-g-either-the-complete-graph-or-its-complemen%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
