직관 — 연결 하나를 양쪽에서 센다
다섯 사람이 서로 악수한 기록을 그렸다고 하자. 각자 악수한 상대의 수를 적고 모두 더하면, 한 번의 악수가 두 사람의 기록에 각각 들어간다. 사람별 기록의 합과 실제 악수 횟수 사이에는 정확히 두 배의 관계가 생긴다.
같은 두 사람이 여러 번 악수했더라도 ‘서로 악수했는가’만 기록하는 가상 모형이다. 단순 그래프에서 변 하나는 서로 다른 두 꼭짓점에 닿는다. 여러 번의 행동을 각각 다른 변으로 세는 모형은 이번 범위가 아니다.
꼭짓점의 차수는 그 점에 닿은 변의 개수다
꼭짓점의 차수는 그 꼭짓점을 한쪽 끝으로 갖는 변의 수다. 유한한 단순 무방향그래프에서 차수는 0 이상의 정수이고, 꼭짓점이 개이면 최대 이다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 그래프 | graph | 꼭짓점 집합과 변 집합 | |
| 꼭짓점 | vertex | 차수를 셀 대상 하나 | |
| 차수 | degree | 에 닿은 변의 수 | |
| 꼭짓점 수, 변 수 | order, size | 그래프 전체의 두 개수 | |
| 모든 꼭짓점에 대한 합 | sum over vertices | 각 꼭짓점의 값을 한 번씩 더함 |
우리교과서의 차수 표기 와 같은 뜻이다. 단순 그래프에는 중복 변이 없으므로 차수는 그 점과 인접한 꼭짓점의 수와도 같다. 자기 자신을 제외한 개와 모두 인접할 때 식 (1)의 최댓값이 된다. 연결된 변이 하나도 없는 고립점의 차수는 0이다.
앞 글의 가상 전시실 연결 를 다시 보자. 에는 가 닿으므로 차수가 2다. 에는 가 닿으므로 3이다. 같은 방식으로 세면 다음과 같다.
그림 1에서는 각 꼭짓점에 닿은 선만 세어 식 (2)의 다섯 차수를 다시 확인할 수 있다. 차수는 선의 길이나 꺾인 횟수가 아니라 개수다. 꼭짓점마다 인접한 점을 한 줄씩 적은 표가 인접행렬이며, 그 행의 합이 차수다.
figures/degree_counts.py차수가 0인 꼭짓점도 그래프에 포함하나요?
포함한다. 아무 관계도 없는 대상은 차수 0인 고립점으로 남긴다. 삼각형에 고립점 하나를 더하면 꼭짓점은 3개에서 4개로 늘지만, 차수 합 6과 변 3개는 그대로다.
차수의 합은 왜 항상 변 수의 두 배일까?
차수를 모두 더하는 것은 ‘변과 그 끝점의 짝’을 세는 일이다. 어떤 변을 골라도 서로 다른 끝점이 정확히 둘이므로, 그 변은 전체 합에 정확히 2를 보탠다. 변마다 같은 일이 일어나므로 다음 악수 정리가 성립한다.
그림 2는 그 짝을 표로 늘어놓은 것이다. 가로줄은 변, 세로줄은 꼭짓점이고, 변의 끝점인 칸에 점을 찍었다. 같은 점 10개를 가로로 세면 변마다 2개씩이라 이고, 세로로 세면 꼭짓점마다 차수라 이다. 같은 대상을 두 방향으로 센 값이므로 두 합은 같을 수밖에 없다.
figures/incidence_table.py식 (2)는 정리를 확인한 한 사례이고, 끝점 세기가 모든 유한한 단순 무방향그래프에 대한 이유다. 그래프가 연결되지 않아도 각 변에 끝점이 둘이라는 사실은 변하지 않는다. 우리교과서처럼 변을 하나씩 더해 가며 봐도 같다. 변 하나를 그으면 양 끝 차수가 1씩 늘어 합이 2 늘어난다.
차수가 인 그래프라면 합이 이므로 변은 개다. 반대로 변이 7개이면 차수의 합은 14다. 변의 개수를 구할 때는 꼭짓점별 차수를 더한 뒤 반드시 2로 나눈다.
모든 꼭짓점의 차수가 같으면 변은 몇 개일까?
꼭짓점 개의 차수가 모두 이면 차수의 합은 다. 식 (3)에 넣으면 그래프를 그리지 않고도 변의 수가 나온다.
정육면체의 꼭짓점과 모서리를 그래프로 보면 꼭짓점 8개의 차수가 모두 3이다. 식 (4)에서 이며, 실제 모서리 수와 같다.
서로 다른 모든 두 꼭짓점이 인접하는 그래프를 완전그래프라 하고, 꼭짓점이 개이면 으로 쓴다. 각 꼭짓점이 나머지 개와 모두 이어지므로 을 식 (4)에 넣는다.
그림 3 위의 는 차수가 모두 4여서 , 변은 10개다. 식 (1)에서 차수는 이하이므로 차수의 합은 이하다. 그래서 꼭짓점 개인 단순 그래프의 변은 식 (5)의 값 이하다. 이 최댓값은 모든 차수가 인 완전그래프에서만 나온다.
꼭짓점을 두 집단으로 나누고, 다른 집단의 두 점은 모두 잇되 같은 집단끼리는 잇지 않은 그래프를 완전이분그래프라 한다. 두 집단의 크기가 이면 로 쓴다. 한쪽 개의 차수는 , 다른 쪽 개의 차수는 여서 합이 이므로 변은 개다.
figures/complete_graph_degrees.py그림 3 아래의 은 로 변이 9개다. 두 그래프는 평면그래프에서 교차 없이 그릴 수 있는지를 따질 때 다시 나온다.
다섯 명이 각자 정확히 세 명과 악수할 수 있나요?
아니다. 다섯 명의 악수 상대 수를 더하면 로 홀수인데, 식 (3)에 따르면 이 합은 악수 횟수의 두 배여서 짝수여야 한다. 여섯 명이라면 가능하다. 그림 3의 처럼 세 명씩 두 편으로 나눠 상대편과만 악수하면 모두 세 명과 악수하고, 악수는 9번이다.
홀수 차수 꼭짓점의 개수도 왜 짝수일까?
짝수 차수들만 더한 값은 짝수다. 식 (3)의 전체 합도 짝수이므로 홀수 차수들만 더한 값 역시 짝수여야 한다. 홀수를 홀수 개 더하면 홀수가 되므로, 홀수 차수 꼭짓점의 개수는 짝수다.
식 (2)에서는 차수 3인 와 차수 1인 , 총 2개다. 차수가 모두 2인 삼각형의 홀수 차수 꼭짓점은 0개이며 0도 짝수다. 파티에서 홀수 명과 악수한 사람의 수가 늘 짝수라는 말도 같은 성질이다.
이 성질은 다음 오일러그래프에서 한붓그리기의 시작점과 끝점을 찾는 데 쓰인다.
홀수 차수 꼭짓점이 정확히 한 개일 수 있나요?
아니다. 유한한 단순 무방향그래프에서 홀수 차수 꼭짓점의 수는 0, 2, 4처럼 짝수다. 홀수 하나에 짝수 여러 개를 더한 합은 홀수여서 짝수인 식 (3)의 합과 같을 수 없다. 기록한 차수 가운데 홀수가 하나뿐이면 어딘가를 빠뜨렸거나 잘못 센 것이다.
합이 짝수이면 원하는 차수 목록을 만들 수 있을까?
항상 그렇지는 않다. 네 꼭짓점 의 차수를 로 요구하면 합은 8이고 모든 값이 0 이상 3 이하이지만, 단순 그래프를 만들 수 없다.
그림 4가 이유다. 차수 3인 와 는 꼭짓점이 4개뿐이므로 나머지 세 점과 모두 이어져야 한다. 그 다섯 변을 그으면 과 는 이미 와 이어져 차수가 2다. 변을 더하면 차수가 늘기만 하므로 1로 내릴 방법이 없다.
figures/forced_degrees.py합이 짝수라는 사실과 식 (1)은 필요조건이다. 그래프를 실제로 구성하거나 다른 논증으로 가능성을 보여야 충분하다. 그림 4의 그래프는 그대로 라는 목록을 실현한다. 합이 같은 짝수라도 목록에 따라 가능 여부가 갈린다.
꼭짓점의 차수를 모두 더하면 변 수의 두 배다. 따라서 홀수 차수 꼭짓점의 수는 짝수이고 완전그래프 의 변은 개이지만, 이 조건만으로 그래프의 존재를 보장하지는 않는다.
같은 차수 목록이면 같은 그래프인가요?
아니다. 여섯 점을 하나의 육각형처럼 이은 그래프와, 서로 떨어진 삼각형 두 개는 모두 변이 6개이고 모든 차수가 2다. 첫 그래프는 연결되고 둘째는 연결되지 않으므로 연결 관계는 다르다.
꼭짓점 차수의 흔한 오해
- 차수의 합이 곧 변의 개수다. — 한 변은 두 끝점의 차수에 하나씩 들어간다. 식 (2)의 합은 10이지만 변은 5개다.
- 차수 합은 연결된 그래프에서만 짝수다. — 변의 양 끝을 세는 이유는 연결성과 무관하다. 서로 떨어진 삼각형 두 개도 합이 12, 변이 6개다.
- 홀수 차수 꼭짓점이 짝수 개라는 말은 홀수 차숫값이 짝수 종류라는 뜻이다. — 세는 대상은 꼭짓점이다. 떨어진 두 변 의 차수는 로 홀수 값은 한 종류지만 홀수 차수 꼭짓점은 4개다.
직접 해보기
- 여섯 꼭짓점의 차수가 이다. 변의 개수와 홀수 차수 꼭짓점 수를 구하시오. 가능하다면 변 목록도 하나 구성하시오.
- 변이 8개이고, 다섯 꼭짓점의 차수가 차례로 이다. 를 구하시오.
- 다섯 꼭짓점의 차수가 인 단순 그래프가 가능한지 설명하시오.
- 완전이분그래프 의 차수 목록과 변의 개수를 구하시오.
- 정팔면체의 꼭짓점 6개는 차수가 모두 4이다. 모서리의 개수를 식 (4)로 구하시오. 또 꼭짓점 7개인 완전그래프 의 변의 개수를 구하시오.
답과 풀이
- 합은 이므로 변은 개다. 홀수 차수 꼭짓점은 에 해당하는 4개다. 꼭짓점을 라 하면 가 한 구성이다.
- 전체 합은 이므로 다. 단순 그래프의 상한 4도 넘지 않으며, 변 가 이 목록을 실제로 만든다.
- 불가능하다. 차수 4인 세 점은 다른 모든 점과 인접한다. 나머지 두 점의 차수도 적어도 3이 되어 요구한 1과 모순이다. 합이 14로 짝수라는 조건만으로는 부족하다.
- 두 점 쪽은 차수가 4, 네 점 쪽은 차수가 2여서 목록은 다. 합 16을 2로 나누면 변은 8개이고, 과 같다.
- 식 (4)에서 개다. 은 식 (5)에서 개다.
더 읽기
- 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-02]는 차수 합과 변 수의 관계를 다룬다.
- 우리교과서 이산 수학 공개본 — 인쇄129쪽의 차수 합 정리, 인쇄130~131쪽의 완전그래프·완전이분그래프와 그 변 수를 대조했다. ‘모든 꼭짓점의 차수가 같으면’ 절의 두 그래프가 여기에 기댄다. 본문의 예와 연습은 별도로 구성했다.
- Levin, Graph Theory Introduction — 차수와 차수 합의 이중 계수 논증을 대조한다. 이 글의 불가능한 목록과 새 구성은 별도 검산했다.
- Buckingham, Graph Theory — 「Vertex degrees and the handshaking lemma」와 「Degree sequences」의 악수 정리·차수 목록. 본문은 자기 연결과 중복 변을 제외한 경우로 한정한다.
영상 노트
- 00:00 한 번의 악수를 두 사람의 기록에서 각각 세기
- 00:45 그림 1의 차수를 직접 더해 식 (2) 확인하기
- 01:20 그림 2의 표에서 같은 점 10개를 가로·세로로 세어 식 (3)의 이유 설명하기
- 02:20 식 (4)·(5)로 정육면체, 그림 3의 와 의 변 수 구하기
- 03:20 홀수 차수 개수의 짝수성과, 그림 4로 3, 3, 1, 1이 막히는 이유 보기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 변과 끝점의 표로 본 악수 정리의 이유, 모든 차수가 같은 그래프·완전그래프·완전이분그래프의 변 수, 변 수의 최댓값, 차수 3,3,1,1이 막히는 이유를 그림으로, 질문 블록과 흔한 오해 교체, 해보기 5문항 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림