Quality Learning Support For Better Outcomes
First time here? Checkout the FAQs!
x
MathsGee is Zero-Rated (You do not need data to access) on: Telkom |Dimension Data | Rain | MWEB

0 like 0 dislike
39 views
What is a bridge in graph theory?
in Mathematics by Diamond (81,058 points) | 39 views

1 Answer

0 like 0 dislike
Best answer
An edge e of G is called a bridge if G-e has more components than G.

NB: This definition implies that if G is connected, then G-e is disconnected.

Lemma:
Let G be a connected graph. For some $x, y \in V(G)$, if $e=\{x, y\}$ is a bridge, then G-e has precisely 2 components; Furthermore, x and y are in different components.

Theorem:
An edge e is a bridge of a graph G iff it is not connected in any cycle of G.

Corollary:
If there are 2 distinct paths from vertex u to vertex v in G, then G contains a cycle.
by Diamond (81,058 points)

Related questions

0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 29 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 42 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 42 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 35 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 37 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 21 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 26 views
0 like 0 dislike
1 answer
asked Apr 26, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 28 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 107 views
0 like 0 dislike
1 answer
asked Apr 25, 2020 in Mathematics by MathsGee Diamond (81,058 points) | 23 views

Join the MathsGee Answer Hub community and get study support for success - MathsGee Answer Hub provides answers to subject-specific educational questions for improved outcomes.



On MathsGee Answers, you can:


  1. Ask questions
  2. Answer questions
  3. Comment on Answers
  4. Vote on Questions and Answers
  5. Donate to your favourite users
  6. Create/Take Live Video Lessons

Posting on MathsGee


  1. Remember the human
  2. Behave like you would in real life
  3. Look for the original source of content
  4. Search for duplicates before posting
  5. Read the community's rules
MathsGee Tools

Math Worksheet Generator

Math Algebra Solver

Trigonometry Simulations

Vectors Simulations

Matrix Arithmetic Simulations

Matrix Transformations Simulations

Quadratic Equations Simulations

Probability & Statistics Simulations

PHET Simulations

Visual Statistics

MathsGee ZOOM | eBook