Dtjytyk

What exactly term 'companion plants' means?

Variable completely messes up echoed string

If "dar" means "to give", what does "daros" mean?

Why didn't Héctor fade away after this character died in the movie Coco?

Writing in a Christian voice

What is the relationship between relativity and the Doppler effect?

Am I eligible for the Eurail Youth pass? I am 27.5 years old

Do US professors/group leaders only get a salary, but no group budget?

Practical application of matrices and determinants

Loading the leaflet Map in Lightning Web Component

Does the attack bonus from a Masterwork weapon stack with the attack bonus from Masterwork ammunition?

What does "^L" mean in C?

Print last inputted byte

Calculate the frequency of characters in a string

Hausdorff dimension of the boundary of fibres of Lipschitz maps

World War I as a war of liberals against authoritarians?

Pronounciation of the combination "st" in spanish accents

Brake pads destroying wheels

Recruiter wants very extensive technical details about all of my previous work

Maths symbols and unicode-math input inside siunitx commands

How can an organ that provides biological immortality be unable to regenerate?

Is it true that good novels will automatically sell themselves on Amazon (and so on) and there is no need for one to waste time promoting?

Using Past-Perfect interchangeably with the Past Continuous

Could Sinn Fein swing any Brexit vote in Parliament?

If every vertex in a graph G has degree >=d, then show that G must contain a circuit of length at least d+1. (Applied Combinatorics, 1.5.8)

Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3?Suppose that every vertex of $G$ has degree at least 3. Prove that $G$ has a cycle of even length.Nearest neighbour algorithm (or so I think).min degree at least $n+1/2$, every edge on Hamilton cycleLongest path technique of proving a graph theory problem# edges = # of vertices implies unique simple cycleShow that a graph with with exactly 1 vertex of degree 1, contains a cycleproving Hamiltonian path doesnt existProof that every degree-at-least-2 graph has a cycle with at most $2lg n+1$ vertices of degree more than 2Edmond's Blossom algorithm explanation

1

$begingroup$

There are two questions that essentially asked the same thing. One is categorized as a repetition but I just don't feel the other one's answers are valid.
Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$
For the first answer that got 9 upvotes, it doesn't explain why every neighbour of a vertex is on the path P. Path doesn't allow repeating vertices so I don't see explicitly how one can travel from the node to all its neighbors and back without going through the node itself. If it travels outside the picture, say goes on to another node and tries to come back, I don't see how it can do that explicitly either.
Any help appreciated.

graph-theory

share|cite|improve this question

edited Apr 13 '17 at 12:20

Community♦

1

asked May 26 '16 at 0:25

Mikety2520Mikety2520

62

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If you consider the case when $G$ is a cycle, then you can visit both neighbors of $v_0$ by going all the way along the cycle $G$. Yes, you are allowed to visit other nodes along the way.
  $endgroup$
  – angryavian
  May 26 '16 at 0:37
  
  
  

  
  
  
  

add a comment | 

1

$begingroup$

There are two questions that essentially asked the same thing. One is categorized as a repetition but I just don't feel the other one's answers are valid.
Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$
For the first answer that got 9 upvotes, it doesn't explain why every neighbour of a vertex is on the path P. Path doesn't allow repeating vertices so I don't see explicitly how one can travel from the node to all its neighbors and back without going through the node itself. If it travels outside the picture, say goes on to another node and tries to come back, I don't see how it can do that explicitly either.
Any help appreciated.

graph-theory

share|cite|improve this question

edited Apr 13 '17 at 12:20

Community♦

1

asked May 26 '16 at 0:25

Mikety2520Mikety2520

62

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If you consider the case when $G$ is a cycle, then you can visit both neighbors of $v_0$ by going all the way along the cycle $G$. Yes, you are allowed to visit other nodes along the way.
  $endgroup$
  – angryavian
  May 26 '16 at 0:37
  
  
  

  
  
  
  

add a comment | 

$begingroup$

There are two questions that essentially asked the same thing. One is categorized as a repetition but I just don't feel the other one's answers are valid.
Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$
For the first answer that got 9 upvotes, it doesn't explain why every neighbour of a vertex is on the path P. Path doesn't allow repeating vertices so I don't see explicitly how one can travel from the node to all its neighbors and back without going through the node itself. If it travels outside the picture, say goes on to another node and tries to come back, I don't see how it can do that explicitly either.
Any help appreciated.

graph-theory

share|cite|improve this question

edited Apr 13 '17 at 12:20

Community♦

1

asked May 26 '16 at 0:25

Mikety2520Mikety2520

62

$endgroup$

share|cite|improve this question

edited Apr 13 '17 at 12:20

Community♦

1

asked May 26 '16 at 0:25

Mikety2520Mikety2520

62

share|cite|improve this question

edited Apr 13 '17 at 12:20

Community♦

1

asked May 26 '16 at 0:25

Mikety2520Mikety2520

62

edited Apr 13 '17 at 12:20

Community♦

1

edited Apr 13 '17 at 12:20

Community♦

1

asked May 26 '16 at 0:25

Mikety2520Mikety2520

62

asked May 26 '16 at 0:25

Mikety2520Mikety2520

62

1 Answer
1

active

oldest

votes

0

$begingroup$

We prove by induction on $d$. If $d = 1$ there is an edge, and this is the
needed path. Suppose $d ≥ 2$, the result is true for $d < D$, and minimum degree of your graph is $d$.
By the induction hypothesis $G$ has a path $P$ of length at least $d − 1$. If
the length of $P$ is at least $D$, then we’re done. So suppose the length is $D − 1$ and
the sequence of vertices is $v_1, . . . , v_D$. The vertex $v_1$ has at least $D$ adjacent vertices, so there is a vertex $w$ which is adjacent to $v_1$, but is not on the path
$P$. Thus $w, v_1, . . . , v_D$ is a path in $G$ with $D$ edges.

Now we prove that if $D ≥ 2$, the $G$ has a cycle of length at least $D + 1$.
Let $P = v_0, v_1, . . . , v_m$ be a path of maximum length in $G$. The argument
of previous part shows that $m ≥ D$, and that every vertex $w_d$ adjacent to $v_0$ is
on the path $P$. Suppose, starting at $v_0$, the vertices $w_d$ appear in the order
$w_1, . . . , w_L$. Then extend the path $v_0, . . . , w_L$ to a cycle by adding the edge
$w_Lv_0$. The resulting cycle has at least $D + 1$ vertices, and thus has length at
least $D + 1$.

share|cite|improve this answer

answered May 26 '16 at 0:39

KenKen

42028

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot for answering and the explanation. I still have a question: why do you know every vertex on wd adjacent to v0 is on the path P? I mean, you don't necessarily know all d-1 edges that are adjacent to v0 forms a path by themselves right?
  $endgroup$
  – Mikety2520
  May 26 '16 at 2:50
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Because we assumed that path $P = v_0, cdots, v_m$ has maximum length in $G.$ So if there exist a vertex $w_d$ which is not adjacent to $v_0$ and also it is not on the path $P$, then you can make a longer path only by adding that vertex to $P$ and this is contradiction with the assumption that path $P$ has maximum length in your graph.
  $endgroup$
  – Ken
  May 26 '16 at 16:24
  

  
  
  
  

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%2f1800213%2fif-every-vertex-in-a-graph-g-has-degree-d-then-show-that-g-must-contain-a-cir%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

We prove by induction on $d$. If $d = 1$ there is an edge, and this is the
needed path. Suppose $d ≥ 2$, the result is true for $d < D$, and minimum degree of your graph is $d$.
By the induction hypothesis $G$ has a path $P$ of length at least $d − 1$. If
the length of $P$ is at least $D$, then we’re done. So suppose the length is $D − 1$ and
the sequence of vertices is $v_1, . . . , v_D$. The vertex $v_1$ has at least $D$ adjacent vertices, so there is a vertex $w$ which is adjacent to $v_1$, but is not on the path
$P$. Thus $w, v_1, . . . , v_D$ is a path in $G$ with $D$ edges.

Now we prove that if $D ≥ 2$, the $G$ has a cycle of length at least $D + 1$.
Let $P = v_0, v_1, . . . , v_m$ be a path of maximum length in $G$. The argument
of previous part shows that $m ≥ D$, and that every vertex $w_d$ adjacent to $v_0$ is
on the path $P$. Suppose, starting at $v_0$, the vertices $w_d$ appear in the order
$w_1, . . . , w_L$. Then extend the path $v_0, . . . , w_L$ to a cycle by adding the edge
$w_Lv_0$. The resulting cycle has at least $D + 1$ vertices, and thus has length at
least $D + 1$.

share|cite|improve this answer

answered May 26 '16 at 0:39

KenKen

42028

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot for answering and the explanation. I still have a question: why do you know every vertex on wd adjacent to v0 is on the path P? I mean, you don't necessarily know all d-1 edges that are adjacent to v0 forms a path by themselves right?
  $endgroup$
  – Mikety2520
  May 26 '16 at 2:50
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Because we assumed that path $P = v_0, cdots, v_m$ has maximum length in $G.$ So if there exist a vertex $w_d$ which is not adjacent to $v_0$ and also it is not on the path $P$, then you can make a longer path only by adding that vertex to $P$ and this is contradiction with the assumption that path $P$ has maximum length in your graph.
  $endgroup$
  – Ken
  May 26 '16 at 16:24
  

  
  
  
  

add a comment | 

0

$begingroup$

We prove by induction on $d$. If $d = 1$ there is an edge, and this is the
needed path. Suppose $d ≥ 2$, the result is true for $d < D$, and minimum degree of your graph is $d$.
By the induction hypothesis $G$ has a path $P$ of length at least $d − 1$. If
the length of $P$ is at least $D$, then we’re done. So suppose the length is $D − 1$ and
the sequence of vertices is $v_1, . . . , v_D$. The vertex $v_1$ has at least $D$ adjacent vertices, so there is a vertex $w$ which is adjacent to $v_1$, but is not on the path
$P$. Thus $w, v_1, . . . , v_D$ is a path in $G$ with $D$ edges.

Now we prove that if $D ≥ 2$, the $G$ has a cycle of length at least $D + 1$.
Let $P = v_0, v_1, . . . , v_m$ be a path of maximum length in $G$. The argument
of previous part shows that $m ≥ D$, and that every vertex $w_d$ adjacent to $v_0$ is
on the path $P$. Suppose, starting at $v_0$, the vertices $w_d$ appear in the order
$w_1, . . . , w_L$. Then extend the path $v_0, . . . , w_L$ to a cycle by adding the edge
$w_Lv_0$. The resulting cycle has at least $D + 1$ vertices, and thus has length at
least $D + 1$.

share|cite|improve this answer

answered May 26 '16 at 0:39

KenKen

42028

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot for answering and the explanation. I still have a question: why do you know every vertex on wd adjacent to v0 is on the path P? I mean, you don't necessarily know all d-1 edges that are adjacent to v0 forms a path by themselves right?
  $endgroup$
  – Mikety2520
  May 26 '16 at 2:50
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Because we assumed that path $P = v_0, cdots, v_m$ has maximum length in $G.$ So if there exist a vertex $w_d$ which is not adjacent to $v_0$ and also it is not on the path $P$, then you can make a longer path only by adding that vertex to $P$ and this is contradiction with the assumption that path $P$ has maximum length in your graph.
  $endgroup$
  – Ken
  May 26 '16 at 16:24
  

  
  
  
  

add a comment | 

$begingroup$

We prove by induction on $d$. If $d = 1$ there is an edge, and this is the
needed path. Suppose $d ≥ 2$, the result is true for $d < D$, and minimum degree of your graph is $d$.
By the induction hypothesis $G$ has a path $P$ of length at least $d − 1$. If
the length of $P$ is at least $D$, then we’re done. So suppose the length is $D − 1$ and
the sequence of vertices is $v_1, . . . , v_D$. The vertex $v_1$ has at least $D$ adjacent vertices, so there is a vertex $w$ which is adjacent to $v_1$, but is not on the path
$P$. Thus $w, v_1, . . . , v_D$ is a path in $G$ with $D$ edges.

Now we prove that if $D ≥ 2$, the $G$ has a cycle of length at least $D + 1$.
Let $P = v_0, v_1, . . . , v_m$ be a path of maximum length in $G$. The argument
of previous part shows that $m ≥ D$, and that every vertex $w_d$ adjacent to $v_0$ is
on the path $P$. Suppose, starting at $v_0$, the vertices $w_d$ appear in the order
$w_1, . . . , w_L$. Then extend the path $v_0, . . . , w_L$ to a cycle by adding the edge
$w_Lv_0$. The resulting cycle has at least $D + 1$ vertices, and thus has length at
least $D + 1$.

share|cite|improve this answer

answered May 26 '16 at 0:39

KenKen

42028

$endgroup$

share|cite|improve this answer

answered May 26 '16 at 0:39

KenKen

42028

answered May 26 '16 at 0:39

KenKen

42028

answered May 26 '16 at 0:39

KenKen

42028