Fdtxjr

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

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

How can I track script which gives me "command not found" right after the login?

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

Are ETF trackers fundamentally better than individual stocks?

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

How could a scammer know the apps on my phone / iTunes account?

Interplanetary conflict, some disease destroys the ability to understand or appreciate music

Property of summation

Why is the President allowed to veto a cancellation of emergency powers?

Gravity magic - How does it work?

Look at your watch and tell me what time is it. vs Look at your watch and tell me what time it is

My adviser wants to be the first author

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

What should tie a collection of short-stories together?

Is it possible to upcast ritual spells?

Charles Hockett - 'F' article?

In a future war, an old lady is trying to raise a boy but one of the weapons has made everyone deaf

Brexit - No Deal Rejection

A limit with limit zero everywhere must be zero somewhere

Why do Australian milk farmers need to protest supermarkets' milk price?

Who is flying the vertibirds?

SOQL: Populate a Literal List in WHERE IN Clause

Why does Bach not break the rules here?

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