Remove bridges to make finding a path impossible.

Clash Royale CLAN TAG#URR8PPP

up vote
5
down vote

favorite

1

Here's a question relating to graph theory that was asked in the International Kangaroo Maths Contest 2017. I am a college student and have a very less knowhow of graph theory. The question goes like this:

We have $10$ islands that have been connected by $15$ bridges.

What is the smallest number of bridges that may be eliminated so that it becomes impossible to get from $A$ to $B$ by bridge?

Answer: The answer given in the key is $3$, but I can't see how that might be.

What I did:

First of all I transferred the problem into graphical terms.

We have $10$ vertices connected by $15$ edges.

What is the smallest possible number of edges that when removed to make it impossible to find a path from $A$ to $B$?

So I considered that we can do this by 'isolating' either $A$ or $B$. This may be done by removing all the edges corresponding to either $A$ or $B$. The number of edges corresponding to $A$ is $4$ while those with $B$ are $5$. So the smallest number that can be the answer is $4$. So what is wrong with this method? How can be the answer, $3$, be reached?

Thanks for the attention.

graph-theory contest-math

share|cite|improve this question

edited 1 hour ago

Theo Bendit

15.3k12146

asked 1 hour ago

Faiq Irfan

424215

add a comment | 

up vote
5
down vote

favorite

1

Here's a question relating to graph theory that was asked in the International Kangaroo Maths Contest 2017. I am a college student and have a very less knowhow of graph theory. The question goes like this:

We have $10$ islands that have been connected by $15$ bridges.

What is the smallest number of bridges that may be eliminated so that it becomes impossible to get from $A$ to $B$ by bridge?

Answer: The answer given in the key is $3$, but I can't see how that might be.

What I did:

First of all I transferred the problem into graphical terms.

We have $10$ vertices connected by $15$ edges.

What is the smallest possible number of edges that when removed to make it impossible to find a path from $A$ to $B$?

So I considered that we can do this by 'isolating' either $A$ or $B$. This may be done by removing all the edges corresponding to either $A$ or $B$. The number of edges corresponding to $A$ is $4$ while those with $B$ are $5$. So the smallest number that can be the answer is $4$. So what is wrong with this method? How can be the answer, $3$, be reached?

Thanks for the attention.

graph-theory contest-math

share|cite|improve this question

edited 1 hour ago

Theo Bendit

15.3k12146

asked 1 hour ago

Faiq Irfan

424215

add a comment | 

up vote
5
down vote

favorite

1

up vote
5
down vote

favorite

1

1

Here's a question relating to graph theory that was asked in the International Kangaroo Maths Contest 2017. I am a college student and have a very less knowhow of graph theory. The question goes like this:

We have $10$ islands that have been connected by $15$ bridges.

What is the smallest number of bridges that may be eliminated so that it becomes impossible to get from $A$ to $B$ by bridge?

Answer: The answer given in the key is $3$, but I can't see how that might be.

What I did:

First of all I transferred the problem into graphical terms.

We have $10$ vertices connected by $15$ edges.

What is the smallest possible number of edges that when removed to make it impossible to find a path from $A$ to $B$?

So I considered that we can do this by 'isolating' either $A$ or $B$. This may be done by removing all the edges corresponding to either $A$ or $B$. The number of edges corresponding to $A$ is $4$ while those with $B$ are $5$. So the smallest number that can be the answer is $4$. So what is wrong with this method? How can be the answer, $3$, be reached?

Thanks for the attention.

graph-theory contest-math

share|cite|improve this question

edited 1 hour ago

Theo Bendit

15.3k12146

asked 1 hour ago

Faiq Irfan

424215

Here's a question relating to graph theory that was asked in the International Kangaroo Maths Contest 2017. I am a college student and have a very less knowhow of graph theory. The question goes like this:

We have $10$ islands that have been connected by $15$ bridges.

What is the smallest number of bridges that may be eliminated so that it becomes impossible to get from $A$ to $B$ by bridge?

Answer: The answer given in the key is $3$, but I can't see how that might be.

What I did:

First of all I transferred the problem into graphical terms.

We have $10$ vertices connected by $15$ edges.

What is the smallest possible number of edges that when removed to make it impossible to find a path from $A$ to $B$?

So I considered that we can do this by 'isolating' either $A$ or $B$. This may be done by removing all the edges corresponding to either $A$ or $B$. The number of edges corresponding to $A$ is $4$ while those with $B$ are $5$. So the smallest number that can be the answer is $4$. So what is wrong with this method? How can be the answer, $3$, be reached?

Thanks for the attention.

graph-theory contest-math

graph-theory contest-math

share|cite|improve this question

edited 1 hour ago

Theo Bendit

15.3k12146

asked 1 hour ago

Faiq Irfan

424215

share|cite|improve this question

edited 1 hour ago

Theo Bendit

15.3k12146

asked 1 hour ago

Faiq Irfan

424215

share|cite|improve this question

share|cite|improve this question

edited 1 hour ago

Theo Bendit

15.3k12146

edited 1 hour ago

Theo Bendit

15.3k12146

edited 1 hour ago

Theo Bendit

15.3k12146

15.3k12146

asked 1 hour ago

Faiq Irfan

424215

asked 1 hour ago

Faiq Irfan

424215

asked 1 hour ago

Faiq Irfan

424215

424215

add a comment | 

add a comment | 

3 Answers
3

active

oldest

votes

up vote
2
down vote

By removing the red lines $A$ and $B$ are isolated; in other words: no path is possible from $A$ to $B$.

share|cite|improve this answer

answered 1 hour ago

MathFun123

305

• 
  
  
  

  
  

  
  
  
  
  
  

  
  One could add this is called a minimal A-B cut if you want to find more info online.
  – Michal Adamaszek
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
2
down vote

MathFun123's answer shows that it is possible to remove three edges in this way, but not that three is the minimum.

To see that you can't do it with less than three, consider the following.

There are three completely separate paths from A to B shown. In order to cut off B from A, you need to remove at least one red edge to destroy the red path, and similarly at least one blue edge and at least one green edge. So at least three are needed.

share|cite|improve this answer

answered 1 hour ago

Especially Lime

20.3k22554

add a comment | 

up vote
0
down vote

I label the vertices this way : I start at $A=V_1$, then go around the graph clockwise (so that $B=V_6$). The vertex at the center of the graph is $V_10$. Then, you can remove the edges $V_3V_4$, $V_1V_10$ and $V_9V_1$. $A$ and $B$ are not connected anymore.

share|cite|improve this answer

answered 1 hour ago

Tony Morel

1

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2970514%2fremove-bridges-to-make-finding-a-path-impossible%23new-answer', 'question_page');

);

Post as a guest

Name Email

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

By removing the red lines $A$ and $B$ are isolated; in other words: no path is possible from $A$ to $B$.

share|cite|improve this answer

answered 1 hour ago

MathFun123

305

• 
  
  
  

  
  

  
  
  
  
  
  

  
  One could add this is called a minimal A-B cut if you want to find more info online.
  – Michal Adamaszek
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
2
down vote

By removing the red lines $A$ and $B$ are isolated; in other words: no path is possible from $A$ to $B$.

share|cite|improve this answer

answered 1 hour ago

MathFun123

305

• 
  
  
  

  
  

  
  
  
  
  
  

  
  One could add this is called a minimal A-B cut if you want to find more info online.
  – Michal Adamaszek
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

By removing the red lines $A$ and $B$ are isolated; in other words: no path is possible from $A$ to $B$.

share|cite|improve this answer

answered 1 hour ago

MathFun123

305

By removing the red lines $A$ and $B$ are isolated; in other words: no path is possible from $A$ to $B$.

share|cite|improve this answer

answered 1 hour ago

MathFun123

305

share|cite|improve this answer

share|cite|improve this answer

answered 1 hour ago

MathFun123

305

answered 1 hour ago

MathFun123

305

answered 1 hour ago

MathFun123

305

305

• 
  
  
  

  
  

  
  
  
  
  
  

  
  One could add this is called a minimal A-B cut if you want to find more info online.
  – Michal Adamaszek
  1 hour ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  One could add this is called a minimal A-B cut if you want to find more info online.
  – Michal Adamaszek
  1 hour ago
  

  
  
  
  

One could add this is called a minimal A-B cut if you want to find more info online.
– Michal Adamaszek
1 hour ago

One could add this is called a minimal A-B cut if you want to find more info online.
– Michal Adamaszek
1 hour ago

add a comment | 

up vote
2
down vote

MathFun123's answer shows that it is possible to remove three edges in this way, but not that three is the minimum.

To see that you can't do it with less than three, consider the following.

There are three completely separate paths from A to B shown. In order to cut off B from A, you need to remove at least one red edge to destroy the red path, and similarly at least one blue edge and at least one green edge. So at least three are needed.

share|cite|improve this answer

answered 1 hour ago

Especially Lime

20.3k22554

add a comment | 

up vote
2
down vote

MathFun123's answer shows that it is possible to remove three edges in this way, but not that three is the minimum.

To see that you can't do it with less than three, consider the following.

There are three completely separate paths from A to B shown. In order to cut off B from A, you need to remove at least one red edge to destroy the red path, and similarly at least one blue edge and at least one green edge. So at least three are needed.

share|cite|improve this answer

answered 1 hour ago

Especially Lime

20.3k22554

add a comment | 

up vote
2
down vote

up vote
2
down vote

MathFun123's answer shows that it is possible to remove three edges in this way, but not that three is the minimum.

To see that you can't do it with less than three, consider the following.

There are three completely separate paths from A to B shown. In order to cut off B from A, you need to remove at least one red edge to destroy the red path, and similarly at least one blue edge and at least one green edge. So at least three are needed.

share|cite|improve this answer

answered 1 hour ago

Especially Lime

20.3k22554

MathFun123's answer shows that it is possible to remove three edges in this way, but not that three is the minimum.

To see that you can't do it with less than three, consider the following.

There are three completely separate paths from A to B shown. In order to cut off B from A, you need to remove at least one red edge to destroy the red path, and similarly at least one blue edge and at least one green edge. So at least three are needed.

share|cite|improve this answer

answered 1 hour ago

Especially Lime

20.3k22554

share|cite|improve this answer

share|cite|improve this answer

answered 1 hour ago

Especially Lime

20.3k22554

answered 1 hour ago

Especially Lime

20.3k22554

answered 1 hour ago

Especially Lime

20.3k22554

20.3k22554

add a comment | 

add a comment | 

up vote
0
down vote

I label the vertices this way : I start at $A=V_1$, then go around the graph clockwise (so that $B=V_6$). The vertex at the center of the graph is $V_10$. Then, you can remove the edges $V_3V_4$, $V_1V_10$ and $V_9V_1$. $A$ and $B$ are not connected anymore.

share|cite|improve this answer

answered 1 hour ago

Tony Morel

1

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

add a comment | 

up vote
0
down vote

I label the vertices this way : I start at $A=V_1$, then go around the graph clockwise (so that $B=V_6$). The vertex at the center of the graph is $V_10$. Then, you can remove the edges $V_3V_4$, $V_1V_10$ and $V_9V_1$. $A$ and $B$ are not connected anymore.

share|cite|improve this answer

answered 1 hour ago

Tony Morel

1

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

add a comment | 

up vote
0
down vote

up vote
0
down vote

I label the vertices this way : I start at $A=V_1$, then go around the graph clockwise (so that $B=V_6$). The vertex at the center of the graph is $V_10$. Then, you can remove the edges $V_3V_4$, $V_1V_10$ and $V_9V_1$. $A$ and $B$ are not connected anymore.

share|cite|improve this answer

answered 1 hour ago

Tony Morel

1

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

I label the vertices this way : I start at $A=V_1$, then go around the graph clockwise (so that $B=V_6$). The vertex at the center of the graph is $V_10$. Then, you can remove the edges $V_3V_4$, $V_1V_10$ and $V_9V_1$. $A$ and $B$ are not connected anymore.

share|cite|improve this answer

answered 1 hour ago

Tony Morel

1

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this answer

share|cite|improve this answer

answered 1 hour ago

Tony Morel

1

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 1 hour ago

Tony Morel

1

answered 1 hour ago

Tony Morel

1

1

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

New contributor

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

Tony Morel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2970514%2fremove-bridges-to-make-finding-a-path-impossible%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Name Email

Name Email

Name

Email

Name Email

Name

Email