시험 직전 요약장

정점이 V개인 단순 무방향 그래프에서 다음 조건은 서로 밀접하다.

• 연결이고 간선이 V-1개
• 사이클이 없고 간선이 V-1개
• 임의의 두 정점 사이 단순 경로가 정확히 하나
• 임의의 간선 하나를 제거하면 연결이 끊어짐

단, 조건 일부만 보고 트리라고 단정할 때는 연결성 또는 사이클 여부가 함께 보장되는지 확인한다.

무방향 그래프의 차수 합은 2|E|이다. 완전 무방향 그래프 K_n의 간선 수는 n(n-1)/2, 완전 방향 그래프에서 자기 루프를 제외한 간선 수는 n(n-1)이다.

이분 그래프의 정점을 두 집합으로 나눌 수 있고 같은 집합 내부에는 간선이 없다. 완전 이분 그래프 K_{p,q}의 간선 수는 pq이다.