1

I am reading Mark Weiss's book (2nd Edition) and I can't wrap my head around this thing. How is this even possible. If a graph is undirected then there must be a way to visit every node from everyone. From the image (https://algorithms.tutorialhorizon.com/check-if-given-undirected-graph-is-connected-or-not/). If I want to visit any node from 4, I can. The only way, I can't is if I remove the connection to 4. If that happens, how is this a graph (in my mind graph needs to have edges). Can graphs have "dangling vertices"?

ravenspoint
  • 19,093
  • 6
  • 57
  • 103
harrySherlock
  • 29
  • 3
  • A graph is a set of zero or more vertices and zero or more edges. So, no, a graph needn't have edges, or vertices. But a graph can certainly have edges yet lack a path between two given vertices, as @ravenspoint's answer (and your linked material) demonstrates. – Noah Jul 25 '21 at 14:28

1 Answers1

2

Can graphs have "dangling vertices?

Yes. They can also have subgraphs, sets of vertices connected to each other but not connected to the vertices in other subgraphs. These are usually called components.

enter image description here

For more https://en.wikipedia.org/wiki/Component_(graph_theory)

ravenspoint
  • 19,093
  • 6
  • 57
  • 103