기초수학꼭짓점의 차수#355

꼭짓점의 차수

Vertex Degrees

꼭짓점의 차수는 유한한 단순 무방향그래프에서 그 점에 닿은 변의 수다. 차수의 합은 변 수의 두 배라서 홀수 차수 꼭짓점은 짝수 개이고, 완전그래프의 변 수도 이 관계로 구한다. 이 조건만으로 차수 목록의 실현이 보장되지는 않는다.

읽는 시간
약 7분
선수 개념
그래프의 뜻

직관 — 연결 하나를 양쪽에서 센다

직관

다섯 사람이 서로 악수한 기록을 그렸다고 하자. 각자 악수한 상대의 수를 적고 모두 더하면, 한 번의 악수가 두 사람의 기록에 각각 들어간다. 사람별 기록의 합과 실제 악수 횟수 사이에는 정확히 두 배의 관계가 생긴다.

같은 두 사람이 여러 번 악수했더라도 ‘서로 악수했는가’만 기록하는 가상 모형이다. 단순 그래프에서 변 하나는 서로 다른 두 꼭짓점에 닿는다. 여러 번의 행동을 각각 다른 변으로 세는 모형은 이번 범위가 아니다.

꼭짓점의 차수는 그 점에 닿은 변의 개수다

꼭짓점의 차수는 그 꼭짓점을 한쪽 끝으로 갖는 변의 수다. 유한한 단순 무방향그래프에서 차수는 0 이상의 정수이고, 꼭짓점이 nn개이면 최대 n−1n-1이다.

0≤deg⁡(v)≤n−1.(1)0\le\deg(v)\le n-1. \tag{1}
정의
기호이름원어뜻
G=(V,E)G=(V,E)그래프graph꼭짓점 집합과 변 집합
vv꼭짓점vertex차수를 셀 대상 하나
deg⁡(v)\deg(v)차수degreevv에 닿은 변의 수
n,mn,m꼭짓점 수, 변 수order, size그래프 전체의 두 개수
∑v∈V\sum_{v\in V}모든 꼭짓점에 대한 합sum over vertices각 꼭짓점의 값을 한 번씩 더함

우리교과서의 차수 표기 deg⁡(v)\deg(v)와 같은 뜻이다. 단순 그래프에는 중복 변이 없으므로 차수는 그 점과 인접한 꼭짓점의 수와도 같다. 자기 자신을 제외한 n−1n-1개와 모두 인접할 때 식 (1)의 최댓값이 된다. 연결된 변이 하나도 없는 고립점의 차수는 0이다.

앞 글의 가상 전시실 연결 AB,AC,BC,CD,DEAB,AC,BC,CD,DE를 다시 보자. AA에는 AB,ACAB,AC가 닿으므로 차수가 2다. CC에는 AC,BC,CDAC,BC,CD가 닿으므로 3이다. 같은 방식으로 세면 다음과 같다.

(deg⁡(A),deg⁡(B),deg⁡(C),deg⁡(D),deg⁡(E))=(2,2,3,2,1),2+2+3+2+1=10=2×5.(2)(\deg(A),\deg(B),\deg(C),\deg(D),\deg(E))=(2,2,3,2,1), \qquad 2+2+3+2+1=10=2\times5. \tag{2}

그림 1에서는 각 꼭짓점에 닿은 선만 세어 식 (2)의 다섯 차수를 다시 확인할 수 있다. 차수는 선의 길이나 꺾인 횟수가 아니라 개수다. 꼭짓점마다 인접한 점을 한 줄씩 적은 표가 인접행렬이며, 그 행의 합이 차수다.

다섯 변의 양 끝점을 세어 차수를 표시했다. 꼭짓점 옆의 숫자는 그 점에 닿은 변의 수이며, 모든 숫자의 합은 10이다.
그림 1 다섯 변의 양 끝점을 세어 차수를 표시했다. 꼭짓점 옆의 숫자는 그 점에 닿은 변의 수이며, 모든 숫자의 합은 10이다. figures/degree_counts.py

차수가 0인 꼭짓점도 그래프에 포함하나요?

포함한다. 아무 관계도 없는 대상은 차수 0인 고립점으로 남긴다. 삼각형에 고립점 하나를 더하면 꼭짓점은 3개에서 4개로 늘지만, 차수 합 6과 변 3개는 그대로다.

차수의 합은 왜 항상 변 수의 두 배일까?

차수를 모두 더하는 것은 ‘변과 그 끝점의 짝’을 세는 일이다. 어떤 변을 골라도 서로 다른 끝점이 정확히 둘이므로, 그 변은 전체 합에 정확히 2를 보탠다. 변마다 같은 일이 일어나므로 다음 악수 정리가 성립한다.

∑v∈Vdeg⁡(v)=2m.(3)\sum_{v\in V}\deg(v)=2m. \tag{3}

그림 2는 그 짝을 표로 늘어놓은 것이다. 가로줄은 변, 세로줄은 꼭짓점이고, 변의 끝점인 칸에 점을 찍었다. 같은 점 10개를 가로로 세면 변마다 2개씩이라 2×52\times5이고, 세로로 세면 꼭짓점마다 차수라 2+2+3+2+12+2+3+2+1이다. 같은 대상을 두 방향으로 센 값이므로 두 합은 같을 수밖에 없다.

식 (2)의 그래프에서 가로줄은 다섯 변, 세로줄은 다섯 꼭짓점이다. 변의 끝점인 칸에만 점을 찍었다. 오른쪽 열은 가로줄마다 센 점의 수 2이고, 아래 행은 세로줄마다 센 점의 수인 차수다. 두 방향의 합은 모두 10이다.
그림 2 식 (2)의 그래프에서 가로줄은 다섯 변, 세로줄은 다섯 꼭짓점이다. 변의 끝점인 칸에만 점을 찍었다. 오른쪽 열은 가로줄마다 센 점의 수 2이고, 아래 행은 세로줄마다 센 점의 수인 차수다. 두 방향의 합은 모두 10이다. figures/incidence_table.py

식 (2)는 정리를 확인한 한 사례이고, 끝점 세기가 모든 유한한 단순 무방향그래프에 대한 이유다. 그래프가 연결되지 않아도 각 변에 끝점이 둘이라는 사실은 변하지 않는다. 우리교과서처럼 변을 하나씩 더해 가며 봐도 같다. 변 하나를 그으면 양 끝 차수가 1씩 늘어 합이 2 늘어난다.

차수가 3,3,2,2,23,3,2,2,2인 그래프라면 합이 1212이므로 변은 12÷2=612\div2=6개다. 반대로 변이 7개이면 차수의 합은 14다. 변의 개수를 구할 때는 꼭짓점별 차수를 더한 뒤 반드시 2로 나눈다.

모든 꼭짓점의 차수가 같으면 변은 몇 개일까?

꼭짓점 nn개의 차수가 모두 kk이면 차수의 합은 nknk다. 식 (3)에 넣으면 그래프를 그리지 않고도 변의 수가 나온다.

nk=2m,m=nk2.(4)nk=2m,\qquad m=\frac{nk}{2}. \tag{4}

정육면체의 꼭짓점과 모서리를 그래프로 보면 꼭짓점 8개의 차수가 모두 3이다. 식 (4)에서 m=8×3÷2=12m=8\times3\div2=12이며, 실제 모서리 수와 같다.

서로 다른 모든 두 꼭짓점이 인접하는 그래프를 완전그래프라 하고, 꼭짓점이 nn개이면 KnK_n으로 쓴다. 각 꼭짓점이 나머지 n−1n-1개와 모두 이어지므로 k=n−1k=n-1을 식 (4)에 넣는다.

m=n(n−1)2.(5)m=\frac{n(n-1)}{2}. \tag{5}

그림 3 위의 K5K_5는 차수가 모두 4여서 5×4=2×105\times4=2\times10, 변은 10개다. 식 (1)에서 차수는 n−1n-1 이하이므로 차수의 합은 n(n−1)n(n-1) 이하다. 그래서 꼭짓점 nn개인 단순 그래프의 변은 식 (5)의 값 이하다. 이 최댓값은 모든 차수가 n−1n-1인 완전그래프에서만 나온다.

꼭짓점을 두 집단으로 나누고, 다른 집단의 두 점은 모두 잇되 같은 집단끼리는 잇지 않은 그래프를 완전이분그래프라 한다. 두 집단의 크기가 p,qp,q이면 Kp,qK_{p,q}로 쓴다. 한쪽 pp개의 차수는 qq, 다른 쪽 qq개의 차수는 pp여서 합이 2pq2pq이므로 변은 pqpq개다.

위는 꼭짓점 5개의 완전그래프 K_5로 모든 차수가 4이고 변은 10개다. 아래는 위아래 세 점씩 두 집단의 완전이분그래프 K_3,3으로 모든 차수가 3이고 변은 9개다. 숫자는 각 꼭짓점의 차수다.
그림 3 위는 꼭짓점 5개의 완전그래프 K5K_5로 모든 차수가 4이고 변은 10개다. 아래는 위아래 세 점씩 두 집단의 완전이분그래프 K3,3K_{3,3}으로 모든 차수가 3이고 변은 9개다. 숫자는 각 꼭짓점의 차수다. figures/complete_graph_degrees.py

그림 3 아래의 K3,3K_{3,3}은 6×3=2×96\times3=2\times9로 변이 9개다. 두 그래프는 평면그래프에서 교차 없이 그릴 수 있는지를 따질 때 다시 나온다.

다섯 명이 각자 정확히 세 명과 악수할 수 있나요?

아니다. 다섯 명의 악수 상대 수를 더하면 5×3=155\times3=15로 홀수인데, 식 (3)에 따르면 이 합은 악수 횟수의 두 배여서 짝수여야 한다. 여섯 명이라면 가능하다. 그림 3의 K3,3K_{3,3}처럼 세 명씩 두 편으로 나눠 상대편과만 악수하면 모두 세 명과 악수하고, 악수는 9번이다.

홀수 차수 꼭짓점의 개수도 왜 짝수일까?

짝수 차수들만 더한 값은 짝수다. 식 (3)의 전체 합도 짝수이므로 홀수 차수들만 더한 값 역시 짝수여야 한다. 홀수를 홀수 개 더하면 홀수가 되므로, 홀수 차수 꼭짓점의 개수는 짝수다.

식 (2)에서는 차수 3인 CC와 차수 1인 EE, 총 2개다. 차수가 모두 2인 삼각형의 홀수 차수 꼭짓점은 0개이며 0도 짝수다. 파티에서 홀수 명과 악수한 사람의 수가 늘 짝수라는 말도 같은 성질이다.

이 성질은 다음 오일러그래프에서 한붓그리기의 시작점과 끝점을 찾는 데 쓰인다.

홀수 차수 꼭짓점이 정확히 한 개일 수 있나요?

아니다. 유한한 단순 무방향그래프에서 홀수 차수 꼭짓점의 수는 0, 2, 4처럼 짝수다. 홀수 하나에 짝수 여러 개를 더한 합은 홀수여서 짝수인 식 (3)의 합과 같을 수 없다. 기록한 차수 가운데 홀수가 하나뿐이면 어딘가를 빠뜨렸거나 잘못 센 것이다.

합이 짝수이면 원하는 차수 목록을 만들 수 있을까?

항상 그렇지는 않다. 네 꼭짓점 P,Q,R,SP,Q,R,S의 차수를 3,3,1,13,3,1,1로 요구하면 합은 8이고 모든 값이 0 이상 3 이하이지만, 단순 그래프를 만들 수 없다.

그림 4가 이유다. 차수 3인 PP와 QQ는 꼭짓점이 4개뿐이므로 나머지 세 점과 모두 이어져야 한다. 그 다섯 변을 그으면 RR과 SS는 이미 P,QP,Q와 이어져 차수가 2다. 변을 더하면 차수가 늘기만 하므로 1로 내릴 방법이 없다.

네 꼭짓점의 차수를 3, 3, 1, 1로 요구할 때 차수 3인 P와 Q가 반드시 가져야 하는 다섯 변을 그었다. 그것만으로 R과 S의 차수가 이미 2가 되어 요구한 1과 다르다.
그림 4 네 꼭짓점의 차수를 3, 3, 1, 1로 요구할 때 차수 3인 P와 Q가 반드시 가져야 하는 다섯 변을 그었다. 그것만으로 R과 S의 차수가 이미 2가 되어 요구한 1과 다르다. figures/forced_degrees.py

합이 짝수라는 사실과 식 (1)은 필요조건이다. 그래프를 실제로 구성하거나 다른 논증으로 가능성을 보여야 충분하다. 그림 4의 그래프는 그대로 3,3,2,23,3,2,2라는 목록을 실현한다. 합이 같은 짝수라도 목록에 따라 가능 여부가 갈린다.

핵심

꼭짓점의 차수를 모두 더하면 변 수의 두 배다. 따라서 홀수 차수 꼭짓점의 수는 짝수이고 완전그래프 KnK_n의 변은 n(n−1)/2n(n-1)/2개이지만, 이 조건만으로 그래프의 존재를 보장하지는 않는다.

같은 차수 목록이면 같은 그래프인가요?

아니다. 여섯 점을 하나의 육각형처럼 이은 그래프와, 서로 떨어진 삼각형 두 개는 모두 변이 6개이고 모든 차수가 2다. 첫 그래프는 연결되고 둘째는 연결되지 않으므로 연결 관계는 다르다.

꼭짓점 차수의 흔한 오해

  • 차수의 합이 곧 변의 개수다. — 한 변은 두 끝점의 차수에 하나씩 들어간다. 식 (2)의 합은 10이지만 변은 5개다.
  • 차수 합은 연결된 그래프에서만 짝수다. — 변의 양 끝을 세는 이유는 연결성과 무관하다. 서로 떨어진 삼각형 두 개도 합이 12, 변이 6개다.
  • 홀수 차수 꼭짓점이 짝수 개라는 말은 홀수 차숫값이 짝수 종류라는 뜻이다. — 세는 대상은 꼭짓점이다. 떨어진 두 변 AB,CDAB,CD의 차수는 1,1,1,11,1,1,1로 홀수 값은 한 종류지만 홀수 차수 꼭짓점은 4개다.

직접 해보기

  1. 여섯 꼭짓점의 차수가 3,2,2,1,1,13,2,2,1,1,1이다. 변의 개수와 홀수 차수 꼭짓점 수를 구하시오. 가능하다면 변 목록도 하나 구성하시오.
  2. 변이 8개이고, 다섯 꼭짓점의 차수가 차례로 4,3,3,2,x4,3,3,2,x이다. xx를 구하시오.
  3. 다섯 꼭짓점의 차수가 4,4,4,1,14,4,4,1,1인 단순 그래프가 가능한지 설명하시오.
  4. 완전이분그래프 K2,4K_{2,4}의 차수 목록과 변의 개수를 구하시오.
  5. 정팔면체의 꼭짓점 6개는 차수가 모두 4이다. 모서리의 개수를 식 (4)로 구하시오. 또 꼭짓점 7개인 완전그래프 K7K_7의 변의 개수를 구하시오.
답과 풀이
  1. 합은 1010이므로 변은 55개다. 홀수 차수 꼭짓점은 3,1,1,13,1,1,1에 해당하는 4개다. 꼭짓점을 A,B,C,D,E,FA,B,C,D,E,F라 하면 AB,AC,AD,BE,CFAB,AC,AD,BE,CF가 한 구성이다.
  2. 전체 합은 2×8=162\times8=16이므로 x=16−(4+3+3+2)=4x=16-(4+3+3+2)=4다. 단순 그래프의 상한 4도 넘지 않으며, 변 AB,AC,AD,AE,EB,EC,ED,BCAB,AC,AD,AE,EB,EC,ED,BC가 이 목록을 실제로 만든다.
  3. 불가능하다. 차수 4인 세 점은 다른 모든 점과 인접한다. 나머지 두 점의 차수도 적어도 3이 되어 요구한 1과 모순이다. 합이 14로 짝수라는 조건만으로는 부족하다.
  4. 두 점 쪽은 차수가 4, 네 점 쪽은 차수가 2여서 목록은 4,4,2,2,2,24,4,2,2,2,2다. 합 16을 2로 나누면 변은 8개이고, 2×4=82\times4=8과 같다.
  5. 식 (4)에서 6×4÷2=126\times4\div2=12개다. K7K_7은 식 (5)에서 7×6÷2=217\times6\div2=21개다.

더 읽기

  • 교육부 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의 K5K_5와 K3,3K_{3,3}의 변 수 구하기
  • 03:20 홀수 차수 개수의 짝수성과, 그림 4로 3, 3, 1, 1이 막히는 이유 보기

지도에서의 위치

집합과 원소기초수학그래프의 뜻기초수학꼭짓점의 차수지금 이 페이지오일러그래프기초수학평면그래프기초수학
선수 개념
이 페이지
다음 개념
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 변과 끝점의 표로 본 악수 정리의 이유, 모든 차수가 같은 그래프·완전그래프·완전이분그래프의 변 수, 변 수의 최댓값, 차수 3,3,1,1이 막히는 이유를 그림으로, 질문 블록과 흔한 오해 교체, 해보기 5문항 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림