let the girth of G is at least 2k. Prove that the diameter of Gis at least k.
The question is to prove that if graph G has at least one cycle and that the girth of G (Girth= length of shortest cycle) is at least 2k, then the diameter of G is at least k.
My attempt:
I tried to show both cases if we have even cycle and odd cycle. Let C be the cycle with girth at least 2k. If C is even, then maximum distance between 2 random vertices on C is (2K/2). If C is odd, then the maximum distance between two random vertices on C is at least (2k/2)+1.
Therefore, proved. Any suggestion or modification?
proof-verification graph-theory
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
asked Dec 10 '18 at 3:12
Mera Insan
176
|
show 7 more comments
The question is to prove that if graph G has at least one cycle and that the girth of G (Girth= length of shortest cycle) is at least 2k, then the diameter of G is at least k.
My attempt:
I tried to show both cases if we have even cycle and odd cycle. Let C be the cycle with girth at least 2k. If C is even, then maximum distance between 2 random vertices on C is (2K/2). If C is odd, then the maximum distance between two random vertices on C is at least (2k/2)+1.
Therefore, proved. Any suggestion or modification?
proof-verification graph-theory
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
asked Dec 10 '18 at 3:12
Mera Insan
176
How? Which points should I try to mention?
– Mera Insan
Dec 10 '18 at 3:21
1
Seems to be on the right track but lacking some detail. "If C is even, then maximum distance between 2 random vertices on C is $(2K/2)$". This is true but what happens here that prevents 2 opposing vertices on the cycle of having a shorter path between them outside the cycle?
– MBW
Dec 10 '18 at 3:23
1
That should be enough. Alternatively, you can state directly the proof of why the shortest cycle is an induced subgraph which is short anyway
– MBW
Dec 10 '18 at 3:30
1
Yes. What happens if you have you have two vertices $u, v$ whose distance is $d$ in the cycle and there is another path $P$ joining $u$ and $v$ with distance less than $k-d$ and such that no vertices of $P$ are on the cycle (except for $u$ and $v$)? What can you say about going from $u$ to $v$ in the cycle and then from $v$ to $u$ through $P$?
– MBW
Dec 10 '18 at 3:38
1
Exactly, that is the proof that no such path exists. Thus, if two vertices $u$ and $v$ have distance $k$ in the cycle, they must have that distance in that whole graph
– MBW
Dec 10 '18 at 3:50
|
show 7 more comments
The question is to prove that if graph G has at least one cycle and that the girth of G (Girth= length of shortest cycle) is at least 2k, then the diameter of G is at least k.
My attempt:
I tried to show both cases if we have even cycle and odd cycle. Let C be the cycle with girth at least 2k. If C is even, then maximum distance between 2 random vertices on C is (2K/2). If C is odd, then the maximum distance between two random vertices on C is at least (2k/2)+1.
Therefore, proved. Any suggestion or modification?
proof-verification graph-theory
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
asked Dec 10 '18 at 3:12
Mera Insan
176
The question is to prove that if graph G has at least one cycle and that the girth of G (Girth= length of shortest cycle) is at least 2k, then the diameter of G is at least k.
My attempt:
I tried to show both cases if we have even cycle and odd cycle. Let C be the cycle with girth at least 2k. If C is even, then maximum distance between 2 random vertices on C is (2K/2). If C is odd, then the maximum distance between two random vertices on C is at least (2k/2)+1.
Therefore, proved. Any suggestion or modification?
proof-verification graph-theory
proof-verification graph-theory
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
asked Dec 10 '18 at 3:12
Mera Insan
176
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
asked Dec 10 '18 at 3:12
Mera Insan
176
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
edited Dec 10 '18 at 3:18
Theo Bendit
16.5k12148
16.5k12148
asked Dec 10 '18 at 3:12
Mera Insan
176
asked Dec 10 '18 at 3:12
Mera Insan
176
asked Dec 10 '18 at 3:12
Mera Insan
176
176
How? Which points should I try to mention?
– Mera Insan
Dec 10 '18 at 3:21
1
Seems to be on the right track but lacking some detail. "If C is even, then maximum distance between 2 random vertices on C is $(2K/2)$". This is true but what happens here that prevents 2 opposing vertices on the cycle of having a shorter path between them outside the cycle?
– MBW
Dec 10 '18 at 3:23
1
That should be enough. Alternatively, you can state directly the proof of why the shortest cycle is an induced subgraph which is short anyway
– MBW
Dec 10 '18 at 3:30
1
Yes. What happens if you have you have two vertices $u, v$ whose distance is $d$ in the cycle and there is another path $P$ joining $u$ and $v$ with distance less than $k-d$ and such that no vertices of $P$ are on the cycle (except for $u$ and $v$)? What can you say about going from $u$ to $v$ in the cycle and then from $v$ to $u$ through $P$?
– MBW
Dec 10 '18 at 3:38
1
Exactly, that is the proof that no such path exists. Thus, if two vertices $u$ and $v$ have distance $k$ in the cycle, they must have that distance in that whole graph
– MBW
Dec 10 '18 at 3:50
|
show 7 more comments
How? Which points should I try to mention?
– Mera Insan
Dec 10 '18 at 3:21
1
Seems to be on the right track but lacking some detail. "If C is even, then maximum distance between 2 random vertices on C is $(2K/2)$". This is true but what happens here that prevents 2 opposing vertices on the cycle of having a shorter path between them outside the cycle?
– MBW
Dec 10 '18 at 3:23
1
That should be enough. Alternatively, you can state directly the proof of why the shortest cycle is an induced subgraph which is short anyway
– MBW
Dec 10 '18 at 3:30
1
Yes. What happens if you have you have two vertices $u, v$ whose distance is $d$ in the cycle and there is another path $P$ joining $u$ and $v$ with distance less than $k-d$ and such that no vertices of $P$ are on the cycle (except for $u$ and $v$)? What can you say about going from $u$ to $v$ in the cycle and then from $v$ to $u$ through $P$?
– MBW
Dec 10 '18 at 3:38
1
Exactly, that is the proof that no such path exists. Thus, if two vertices $u$ and $v$ have distance $k$ in the cycle, they must have that distance in that whole graph
– MBW
Dec 10 '18 at 3:50
How? Which points should I try to mention?
– Mera Insan
Dec 10 '18 at 3:21
How? Which points should I try to mention?
– Mera Insan
Dec 10 '18 at 3:21
1
1
Seems to be on the right track but lacking some detail. "If C is even, then maximum distance between 2 random vertices on C is $(2K/2)$". This is true but what happens here that prevents 2 opposing vertices on the cycle of having a shorter path between them outside the cycle?
– MBW
Dec 10 '18 at 3:23
Seems to be on the right track but lacking some detail. "If C is even, then maximum distance between 2 random vertices on C is $(2K/2)$". This is true but what happens here that prevents 2 opposing vertices on the cycle of having a shorter path between them outside the cycle?
– MBW
Dec 10 '18 at 3:23
1
1
That should be enough. Alternatively, you can state directly the proof of why the shortest cycle is an induced subgraph which is short anyway
– MBW
Dec 10 '18 at 3:30
That should be enough. Alternatively, you can state directly the proof of why the shortest cycle is an induced subgraph which is short anyway
– MBW
Dec 10 '18 at 3:30
1
1
Yes. What happens if you have you have two vertices $u, v$ whose distance is $d$ in the cycle and there is another path $P$ joining $u$ and $v$ with distance less than $k-d$ and such that no vertices of $P$ are on the cycle (except for $u$ and $v$)? What can you say about going from $u$ to $v$ in the cycle and then from $v$ to $u$ through $P$?
– MBW
Dec 10 '18 at 3:38
Yes. What happens if you have you have two vertices $u, v$ whose distance is $d$ in the cycle and there is another path $P$ joining $u$ and $v$ with distance less than $k-d$ and such that no vertices of $P$ are on the cycle (except for $u$ and $v$)? What can you say about going from $u$ to $v$ in the cycle and then from $v$ to $u$ through $P$?
– MBW
Dec 10 '18 at 3:38
1
1
Exactly, that is the proof that no such path exists. Thus, if two vertices $u$ and $v$ have distance $k$ in the cycle, they must have that distance in that whole graph
– MBW
Dec 10 '18 at 3:50
Exactly, that is the proof that no such path exists. Thus, if two vertices $u$ and $v$ have distance $k$ in the cycle, they must have that distance in that whole graph
– MBW
Dec 10 '18 at 3:50
|
show 7 more comments
1 Answer
1
active
oldest
votes
Let $C$ be a smallest-length cycle of length $m$ and let $x$ and $y$ be two points furthest from each other on $C$. So the distance between $x$ and $y$ in $C$ is $lfloor frac{m}{2} rfloor$, which, as $m$ is at least $2k$, is at least $k$. So let $P_1$ be a path from $x$ to $y$ on $C$ of length $lfloor frac{m}{2} rfloor$.
Now suppose the diameter of $C$ is less than $lfloor frac{m}{2} rfloor$. Then there is a path $P_2$ of length $l$ $< lfloor frac{m}{2} rfloor$ from $x$ to $y$. Then the graph $P_1 cup P_2$ [a vertex $v$ is in $P_1 cup P_2$ iff $v$ is on either $P_1$ or $P_2$ and an edge is in $P_1 cup P_2$ iff $e$ is in either $P_1$ or $P_2$] has no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ vertices [make sure you see why], and has at least one cycle. [Indeed, as $P_1$ is strictly longer than $P_2$, there is at least one vertex $x'$ in $P_1$ but not on $P_2$. So writing $P=x_1x_2ldots x_{lfloor m/2rfloor}$ let $i$ and $j$ be integers $i+1<j$ such that $x_i$ and $x_j$ is in $P_2$ but $x_{i'} $ is not for $i' in {i+1,ldots , j-1}$. Next let $P'_2$ be the subpath of $P_2$ with endpoints $x_i$ and $x_j$. Then $P'2$ intersects $x_ix_{i+1}ldots x_j$ at precisely $x_i$ and $x_j$, and so $P'_2 cup x_ix_{i+1}ldots x_j$ is a cycle.]
This however, implies that there is a cycle of length no more than the number of vertices in $P_1 cup P_2$ which is no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ $> m$, which is a contradiction.
answered Dec 10 '18 at 17:28
Mike
2,979211
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
});
}
});
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%2f3033390%2flet-the-girth-of-g-is-at-least-2k-prove-that-the-diameter-of-gis-at-least-k%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
Let $C$ be a smallest-length cycle of length $m$ and let $x$ and $y$ be two points furthest from each other on $C$. So the distance between $x$ and $y$ in $C$ is $lfloor frac{m}{2} rfloor$, which, as $m$ is at least $2k$, is at least $k$. So let $P_1$ be a path from $x$ to $y$ on $C$ of length $lfloor frac{m}{2} rfloor$.
Now suppose the diameter of $C$ is less than $lfloor frac{m}{2} rfloor$. Then there is a path $P_2$ of length $l$ $< lfloor frac{m}{2} rfloor$ from $x$ to $y$. Then the graph $P_1 cup P_2$ [a vertex $v$ is in $P_1 cup P_2$ iff $v$ is on either $P_1$ or $P_2$ and an edge is in $P_1 cup P_2$ iff $e$ is in either $P_1$ or $P_2$] has no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ vertices [make sure you see why], and has at least one cycle. [Indeed, as $P_1$ is strictly longer than $P_2$, there is at least one vertex $x'$ in $P_1$ but not on $P_2$. So writing $P=x_1x_2ldots x_{lfloor m/2rfloor}$ let $i$ and $j$ be integers $i+1<j$ such that $x_i$ and $x_j$ is in $P_2$ but $x_{i'} $ is not for $i' in {i+1,ldots , j-1}$. Next let $P'_2$ be the subpath of $P_2$ with endpoints $x_i$ and $x_j$. Then $P'2$ intersects $x_ix_{i+1}ldots x_j$ at precisely $x_i$ and $x_j$, and so $P'_2 cup x_ix_{i+1}ldots x_j$ is a cycle.]
This however, implies that there is a cycle of length no more than the number of vertices in $P_1 cup P_2$ which is no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ $> m$, which is a contradiction.
answered Dec 10 '18 at 17:28
Mike
2,979211
add a comment |
Let $C$ be a smallest-length cycle of length $m$ and let $x$ and $y$ be two points furthest from each other on $C$. So the distance between $x$ and $y$ in $C$ is $lfloor frac{m}{2} rfloor$, which, as $m$ is at least $2k$, is at least $k$. So let $P_1$ be a path from $x$ to $y$ on $C$ of length $lfloor frac{m}{2} rfloor$.
Now suppose the diameter of $C$ is less than $lfloor frac{m}{2} rfloor$. Then there is a path $P_2$ of length $l$ $< lfloor frac{m}{2} rfloor$ from $x$ to $y$. Then the graph $P_1 cup P_2$ [a vertex $v$ is in $P_1 cup P_2$ iff $v$ is on either $P_1$ or $P_2$ and an edge is in $P_1 cup P_2$ iff $e$ is in either $P_1$ or $P_2$] has no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ vertices [make sure you see why], and has at least one cycle. [Indeed, as $P_1$ is strictly longer than $P_2$, there is at least one vertex $x'$ in $P_1$ but not on $P_2$. So writing $P=x_1x_2ldots x_{lfloor m/2rfloor}$ let $i$ and $j$ be integers $i+1<j$ such that $x_i$ and $x_j$ is in $P_2$ but $x_{i'} $ is not for $i' in {i+1,ldots , j-1}$. Next let $P'_2$ be the subpath of $P_2$ with endpoints $x_i$ and $x_j$. Then $P'2$ intersects $x_ix_{i+1}ldots x_j$ at precisely $x_i$ and $x_j$, and so $P'_2 cup x_ix_{i+1}ldots x_j$ is a cycle.]
This however, implies that there is a cycle of length no more than the number of vertices in $P_1 cup P_2$ which is no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ $> m$, which is a contradiction.
answered Dec 10 '18 at 17:28
Mike
2,979211
add a comment |
Let $C$ be a smallest-length cycle of length $m$ and let $x$ and $y$ be two points furthest from each other on $C$. So the distance between $x$ and $y$ in $C$ is $lfloor frac{m}{2} rfloor$, which, as $m$ is at least $2k$, is at least $k$. So let $P_1$ be a path from $x$ to $y$ on $C$ of length $lfloor frac{m}{2} rfloor$.
Now suppose the diameter of $C$ is less than $lfloor frac{m}{2} rfloor$. Then there is a path $P_2$ of length $l$ $< lfloor frac{m}{2} rfloor$ from $x$ to $y$. Then the graph $P_1 cup P_2$ [a vertex $v$ is in $P_1 cup P_2$ iff $v$ is on either $P_1$ or $P_2$ and an edge is in $P_1 cup P_2$ iff $e$ is in either $P_1$ or $P_2$] has no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ vertices [make sure you see why], and has at least one cycle. [Indeed, as $P_1$ is strictly longer than $P_2$, there is at least one vertex $x'$ in $P_1$ but not on $P_2$. So writing $P=x_1x_2ldots x_{lfloor m/2rfloor}$ let $i$ and $j$ be integers $i+1<j$ such that $x_i$ and $x_j$ is in $P_2$ but $x_{i'} $ is not for $i' in {i+1,ldots , j-1}$. Next let $P'_2$ be the subpath of $P_2$ with endpoints $x_i$ and $x_j$. Then $P'2$ intersects $x_ix_{i+1}ldots x_j$ at precisely $x_i$ and $x_j$, and so $P'_2 cup x_ix_{i+1}ldots x_j$ is a cycle.]
This however, implies that there is a cycle of length no more than the number of vertices in $P_1 cup P_2$ which is no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ $> m$, which is a contradiction.
answered Dec 10 '18 at 17:28
Mike
2,979211
Let $C$ be a smallest-length cycle of length $m$ and let $x$ and $y$ be two points furthest from each other on $C$. So the distance between $x$ and $y$ in $C$ is $lfloor frac{m}{2} rfloor$, which, as $m$ is at least $2k$, is at least $k$. So let $P_1$ be a path from $x$ to $y$ on $C$ of length $lfloor frac{m}{2} rfloor$.
Now suppose the diameter of $C$ is less than $lfloor frac{m}{2} rfloor$. Then there is a path $P_2$ of length $l$ $< lfloor frac{m}{2} rfloor$ from $x$ to $y$. Then the graph $P_1 cup P_2$ [a vertex $v$ is in $P_1 cup P_2$ iff $v$ is on either $P_1$ or $P_2$ and an edge is in $P_1 cup P_2$ iff $e$ is in either $P_1$ or $P_2$] has no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ vertices [make sure you see why], and has at least one cycle. [Indeed, as $P_1$ is strictly longer than $P_2$, there is at least one vertex $x'$ in $P_1$ but not on $P_2$. So writing $P=x_1x_2ldots x_{lfloor m/2rfloor}$ let $i$ and $j$ be integers $i+1<j$ such that $x_i$ and $x_j$ is in $P_2$ but $x_{i'} $ is not for $i' in {i+1,ldots , j-1}$. Next let $P'_2$ be the subpath of $P_2$ with endpoints $x_i$ and $x_j$. Then $P'2$ intersects $x_ix_{i+1}ldots x_j$ at precisely $x_i$ and $x_j$, and so $P'_2 cup x_ix_{i+1}ldots x_j$ is a cycle.]
This however, implies that there is a cycle of length no more than the number of vertices in $P_1 cup P_2$ which is no more than $(lfloor frac{m}{2} rfloor +1)+l-1$ $> m$, which is a contradiction.
answered Dec 10 '18 at 17:28
Mike
2,979211
edited Dec 10 '18 at 17:46
answered Dec 10 '18 at 17:28
Mike
2,979211
answered Dec 10 '18 at 17:28
Mike
2,979211
answered Dec 10 '18 at 17:28
Mike
2,979211
2,979211
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3033390%2flet-the-girth-of-g-is-at-least-2k-prove-that-the-diameter-of-gis-at-least-k%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
How? Which points should I try to mention?
– Mera Insan
Dec 10 '18 at 3:21
1
Seems to be on the right track but lacking some detail. "If C is even, then maximum distance between 2 random vertices on C is $(2K/2)$". This is true but what happens here that prevents 2 opposing vertices on the cycle of having a shorter path between them outside the cycle?
– MBW
Dec 10 '18 at 3:23
1
That should be enough. Alternatively, you can state directly the proof of why the shortest cycle is an induced subgraph which is short anyway
– MBW
Dec 10 '18 at 3:30
1
Yes. What happens if you have you have two vertices $u, v$ whose distance is $d$ in the cycle and there is another path $P$ joining $u$ and $v$ with distance less than $k-d$ and such that no vertices of $P$ are on the cycle (except for $u$ and $v$)? What can you say about going from $u$ to $v$ in the cycle and then from $v$ to $u$ through $P$?
– MBW
Dec 10 '18 at 3:38
1
Exactly, that is the proof that no such path exists. Thus, if two vertices $u$ and $v$ have distance $k$ in the cycle, they must have that distance in that whole graph
– MBW
Dec 10 '18 at 3:50