Regular connected graph with at least one bridge.
$begingroup$
We have a connected $k$-regular graph with at least one bridge. For which $k$ does such a graph exsist?
Clearly if $k$ is even, then this graph is Eulerian so it does not have a bridge. So $k$ must be odd.
Also if we delte this bride, then we have components $A$ and $B$ with $a$ and $b$ elements, so we have for component $A$ by handshake lemma $$(a-1)cdot k+1cdot (k-1) = 2alpha$$
where $alpha $ is the number of edges in $A$. So $a$ must be odd. The same is true for $B$.
Now, I don't know how to prove that $k$ is odd is also a sufficient condition. Any idea?
combinatorics graph-theory
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
$endgroup$
add a comment |
$begingroup$
We have a connected $k$-regular graph with at least one bridge. For which $k$ does such a graph exsist?
Clearly if $k$ is even, then this graph is Eulerian so it does not have a bridge. So $k$ must be odd.
Also if we delte this bride, then we have components $A$ and $B$ with $a$ and $b$ elements, so we have for component $A$ by handshake lemma $$(a-1)cdot k+1cdot (k-1) = 2alpha$$
where $alpha $ is the number of edges in $A$. So $a$ must be odd. The same is true for $B$.
Now, I don't know how to prove that $k$ is odd is also a sufficient condition. Any idea?
combinatorics graph-theory
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
$endgroup$
add a comment |
$begingroup$
We have a connected $k$-regular graph with at least one bridge. For which $k$ does such a graph exsist?
Clearly if $k$ is even, then this graph is Eulerian so it does not have a bridge. So $k$ must be odd.
Also if we delte this bride, then we have components $A$ and $B$ with $a$ and $b$ elements, so we have for component $A$ by handshake lemma $$(a-1)cdot k+1cdot (k-1) = 2alpha$$
where $alpha $ is the number of edges in $A$. So $a$ must be odd. The same is true for $B$.
Now, I don't know how to prove that $k$ is odd is also a sufficient condition. Any idea?
combinatorics graph-theory
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
$endgroup$
We have a connected $k$-regular graph with at least one bridge. For which $k$ does such a graph exsist?
Clearly if $k$ is even, then this graph is Eulerian so it does not have a bridge. So $k$ must be odd.
Also if we delte this bride, then we have components $A$ and $B$ with $a$ and $b$ elements, so we have for component $A$ by handshake lemma $$(a-1)cdot k+1cdot (k-1) = 2alpha$$
where $alpha $ is the number of edges in $A$. So $a$ must be odd. The same is true for $B$.
Now, I don't know how to prove that $k$ is odd is also a sufficient condition. Any idea?
combinatorics graph-theory
combinatorics graph-theory
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
edited Jan 8 at 20:11
Maria Mazur
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
asked Jan 8 at 18:57
Maria MazurMaria Mazur
50k1361125
50k1361125
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The special case $k=1$ is uninteresting and easy. So assume $kge 3$.
Take a complete graph on $k+1$ vertices. Select and remove a perfect matching between $k-1$ of them (which is an even number). Each of those $k-1$ vertices now have degree $k-1$; connect them all to a fresh vertex to get their degree back up to $k$. The fresh vertex has exactly one valence left over, which will be your bridge when you connect the graph so far with a second copy of itself.
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
$endgroup$
$begingroup$
Great, how did you come up with this solution?
$endgroup$
– Maria Mazur
Jan 8 at 20:02
add a comment |
$begingroup$
Your observation involving the handshake lemma can be strengthened a bit: $A$ must have degree sequence $(k, k, ldots, k, k-1)$, where there are $a-1$ copies of $k$. A similar statement can be made for $B$. Given two graphs $A$ and $B$ with degree sequences like this, can you construct the desired $k$-regular graph? Do you know some technique for showing that such graphs exist?
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
$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%2f3066580%2fregular-connected-graph-with-at-least-one-bridge%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The special case $k=1$ is uninteresting and easy. So assume $kge 3$.
Take a complete graph on $k+1$ vertices. Select and remove a perfect matching between $k-1$ of them (which is an even number). Each of those $k-1$ vertices now have degree $k-1$; connect them all to a fresh vertex to get their degree back up to $k$. The fresh vertex has exactly one valence left over, which will be your bridge when you connect the graph so far with a second copy of itself.
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
$endgroup$
$begingroup$
Great, how did you come up with this solution?
$endgroup$
– Maria Mazur
Jan 8 at 20:02
add a comment |
$begingroup$
The special case $k=1$ is uninteresting and easy. So assume $kge 3$.
Take a complete graph on $k+1$ vertices. Select and remove a perfect matching between $k-1$ of them (which is an even number). Each of those $k-1$ vertices now have degree $k-1$; connect them all to a fresh vertex to get their degree back up to $k$. The fresh vertex has exactly one valence left over, which will be your bridge when you connect the graph so far with a second copy of itself.
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
$endgroup$
$begingroup$
Great, how did you come up with this solution?
$endgroup$
– Maria Mazur
Jan 8 at 20:02
add a comment |
$begingroup$
The special case $k=1$ is uninteresting and easy. So assume $kge 3$.
Take a complete graph on $k+1$ vertices. Select and remove a perfect matching between $k-1$ of them (which is an even number). Each of those $k-1$ vertices now have degree $k-1$; connect them all to a fresh vertex to get their degree back up to $k$. The fresh vertex has exactly one valence left over, which will be your bridge when you connect the graph so far with a second copy of itself.
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
$endgroup$
The special case $k=1$ is uninteresting and easy. So assume $kge 3$.
Take a complete graph on $k+1$ vertices. Select and remove a perfect matching between $k-1$ of them (which is an even number). Each of those $k-1$ vertices now have degree $k-1$; connect them all to a fresh vertex to get their degree back up to $k$. The fresh vertex has exactly one valence left over, which will be your bridge when you connect the graph so far with a second copy of itself.
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
answered Jan 8 at 19:54
Henning MakholmHenning Makholm
243k17312556
243k17312556
$begingroup$
Great, how did you come up with this solution?
$endgroup$
– Maria Mazur
Jan 8 at 20:02
add a comment |
$begingroup$
Great, how did you come up with this solution?
$endgroup$
– Maria Mazur
Jan 8 at 20:02
$begingroup$
Great, how did you come up with this solution?
$endgroup$
– Maria Mazur
Jan 8 at 20:02
$begingroup$
Great, how did you come up with this solution?
$endgroup$
– Maria Mazur
Jan 8 at 20:02
add a comment |
$begingroup$
Your observation involving the handshake lemma can be strengthened a bit: $A$ must have degree sequence $(k, k, ldots, k, k-1)$, where there are $a-1$ copies of $k$. A similar statement can be made for $B$. Given two graphs $A$ and $B$ with degree sequences like this, can you construct the desired $k$-regular graph? Do you know some technique for showing that such graphs exist?
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
$endgroup$
add a comment |
$begingroup$
Your observation involving the handshake lemma can be strengthened a bit: $A$ must have degree sequence $(k, k, ldots, k, k-1)$, where there are $a-1$ copies of $k$. A similar statement can be made for $B$. Given two graphs $A$ and $B$ with degree sequences like this, can you construct the desired $k$-regular graph? Do you know some technique for showing that such graphs exist?
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
$endgroup$
add a comment |
$begingroup$
Your observation involving the handshake lemma can be strengthened a bit: $A$ must have degree sequence $(k, k, ldots, k, k-1)$, where there are $a-1$ copies of $k$. A similar statement can be made for $B$. Given two graphs $A$ and $B$ with degree sequences like this, can you construct the desired $k$-regular graph? Do you know some technique for showing that such graphs exist?
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
$endgroup$
Your observation involving the handshake lemma can be strengthened a bit: $A$ must have degree sequence $(k, k, ldots, k, k-1)$, where there are $a-1$ copies of $k$. A similar statement can be made for $B$. Given two graphs $A$ and $B$ with degree sequences like this, can you construct the desired $k$-regular graph? Do you know some technique for showing that such graphs exist?
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
answered Jan 8 at 19:02
Gregory J. PuleoGregory J. Puleo
4,65631520
4,65631520
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%2f3066580%2fregular-connected-graph-with-at-least-one-bridge%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
