직접 연결일 필요는 없다
A와 B, B와 C 사이에만 간선이 있어도 세 정점의 그래프는 연결되어 있다. A에서 C로 B를 거쳐 이동할 수 있기 때문이다. A와 C 사이에 직접 간선을 추가해야만 연결되는 것은 아니다.
떨어진 부분이 있으면
{A,B}를 잇는 간선 하나와 {C,D}를 잇는 간선 하나만 있다면 두 무리 사이에는 경로가 없다. 따라서 전체 그래프는 연결되어 있지 않다. 각 부분이 내부적으로 연결되어 있다는 것과 전체 연결성은 다르다.
완전성과 비교
완전 그래프는 서로 다른 모든 정점 쌍이 직접 연결된다. 연결 그래프는 간접 경로도 허용하므로 더 적은 간선으로 조건을 만족할 수 있다. 완전성이 아닌 연결성을 묻는 문제에서는 모든 간선을 채울 필요가 없다.
방향이 있는 경우
유향 그래프에서는 방향을 따라 서로 도달할 수 있는지와 방향을 무시하면 연결되는지를 구별한다. 각각 강연결성과 약연결성 같은 개념으로 다루며 무향 그래프의 연결 조건을 그대로 혼동하지 않는다.
관련 문서
무향 그래프 / 유향 그래프 / 완전 그래프 / 단순 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론)