Advertisement

How can a non-complete graph be connected in graph theory?

Started by December 14, 2014 02:51 AM
1 comment, last by Nicholas Kong 10 years, 2 months ago

My textbook says an undirected is called "connected" if there is a path between every pair of distinct vertices of the graph. An undirected graph that is not connected is "disconnected".

So my interpretation for connected would be that each vertex need to connected with an edge. But wouldn't that make "connected graph" and "complete graph" the same thing?

But that cannot be right then. I think I am struggling to understand "connected".

My interpretation is that complete graph is the same definition as "connected".

Unless this is the actual interpretation: are all "cycles graph" connected then but not complete graph?

A path can consist of multiple edges. What it means for a graph to be connected is that you can go from any vertex to any other by travelling along some set of edges, not just that they are directly connected with a single edge. So, no, a connected graph and a complete graph are very much not the same.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

Advertisement

A path can consist of multiple edges. What it means for a graph to be connected is that you can go from any vertex to any other by travelling along some set of edges, not just that they are directly connected with a single edge. So, no, a connected graph and a complete graph are very much not the same.

Wow it is a subtle difference. You cleared it up my confusion for me so well! Thank you!

This topic is closed to new replies.

Advertisement