2025-11-23T16:49:17.147369

2-Factors in Graphs

Heuvel, Toft

An account of 2-factors in graphs and their history is presented. We give a direct graph-theoretic proof of the 2-Factor Theorem and a new variant of it, and also a new complete characterisation of the maximal graphs without 2-factors. This is based on the important works of Tibor Gallai on 1-factors and of Hans-Boris Belck on k-factors, both published in 1950 and independently containing the theory of alternating chains. We also present an easy proof that a $(2k+1)$-regular graph with at most $2k$ leaves has a 2-factor, and we describe all connected $(2k+1)$-regular graphs with exactly $2k+1$ leaves without a 2-factor. This generalises Julius Petersen's famous theorem, that any 3-regular graph with at most two leaves has a 1-factor, and it generalises the extremal graphs Sylvester discovered for that theorem.

academic

그래프의 2-인수(2-Factors)

기본 정보

논문 ID: 2510.11486
제목: 2-Factors in Graphs
저자: Jan van den Heuvel (런던정경대학교), Bjarne Toft (남덴마크대학교)
분류: math.CO (조합수학)
발표 시간: 2025년 10월 13일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2510.11486

초록

본 논문은 그래프 이론에서 2-인수의 이론 및 그 역사적 발전을 체계적으로 설명한다. 저자들은 Tibor Gallai의 1950년 1-인수에 관한 중요한 업적과 Hans-Boris Belck의 동일 시기 k-인수 연구(둘 다 독립적으로 교대 경로 이론을 포함)에 기반하여, 2-인수 정리의 직접적인 그래프 이론적 증명과 새로운 변형을 제시한다. 또한 2-인수를 포함하지 않는 극대 그래프를 처음으로 완전히 특성화하고, 최대 2k개의 잎을 가진 (2k+1)-정규 그래프는 반드시 2-인수를 가짐을 증명한다. 정확히 2k+1개의 잎을 가지면서 2-인수를 포함하지 않는 모든 연결된 (2k+1)-정규 그래프를 기술한다. 이러한 결과들은 Julius Petersen의 유명한 정리(최대 2개의 잎을 가진 모든 3-정규 그래프는 1-인수를 가짐)와 Sylvester가 발견한 해당 정리의 극값 그래프를 일반화한다.

연구 배경 및 동기

핵심 문제

본 논문은 그래프의 2-인수 문제를 연구한다. 즉, 주어진 그래프에서 2-정규 생성 부분그래프(모든 꼭짓점의 차수가 2인 부분그래프)를 찾는 것이다. 2-인수는 본질적으로 그래프의 서로소 사이클 집합이며, 이는 그래프 이론의 기본 구조이다.

문제의 중요성

이론적 기초성: 사이클과 2-인수는 그래프 이론에서 가장 기본적인 구조이며, 그래프의 성질을 이해하는 데 근본적 의미를 가진다.
역사적 계승: 이 문제는 그래프 이론의 창시자 중 한 명인 Julius Petersen의 1891년 개척적 업적에서 비롯되었다.
이론적 완전성: 관련 연구가 70년 이상 진행되었음에도 불구하고, 2-인수를 포함하지 않는 극대 그래프의 완전한 특성화가 부족했다.

기존 방법의 한계

증명 방법의 복잡성: 초기 증명들은 대수적 방법(예: 반대칭 행렬식)에 크게 의존했다.
구조 특성화의 불완전성: Tutte, Belck, Gallai 등이 인수 이론의 기초를 확립했지만, 극대 그래프에 대한 완전한 설명이 부족했다.
역사적 미해결 문제: Gallai는 2-인수의 일반 이론을 얻었다고 주장했지만 발표하지 않았다.

연구 동기

저자들은 이러한 이론적 공백을 메우고자 하며, Belck과 Gallai의 교대 경로 이론을 사용하여 간결한 그래프 이론적 증명을 제공하고 극대 그래프의 완전한 특성화를 완성하고자 한다.

핵심 기여

2-인수 정리의 간결한 직접 그래프 이론적 증명 제시 - 복잡한 대수적 방법 회피
2-인수를 포함하지 않는 극대 그래프 구조의 처음 완전 특성화 (정리 1.8)
(2k+1)-정규 그래프의 2-인수 존재성 정리 증명 (정리 1.9) - Petersen 고전 정리의 일반화
정확히 2k+1개의 잎을 가지면서 2-인수를 포함하지 않는 모든 (2k+1)-정규 그래프 기술
Hans-Boris Belck의 생애와 기여 발굴 및 소개 - 그래프 이론사의 공백 메우기

방법론 상세 설명

작업 정의

입력: 무방향 유한 그래프 G (중복 간선과 자기 루프 허용) 출력: G가 2-인수를 가지는지 판정 제약: M₂ 클래스에서 작업 (간선 중복도 최대 2, 각 꼭짓점 최대 1개 자기 루프)

핵심 정리

2-인수 정리 (정리 1.7)

그래프 G가 2-인수를 가질 필요충분조건은 임의의 서로소 집합 A, B ⊆ V(G)에 대해, A가 독립 집합이고 C = V(G)(A∪B)일 때, GC에서 A와 홀수 개의 간선으로 연결된 연결 성분의 개수가 다음 이하인 것이다:

-2|A| + 2|B| + e(A,C)

극대 그래프 특성화 (정리 1.8)

G를 M₂ 클래스의 2-인수를 포함하지 않는 극대 그래프라 하고, 다음을 정의하자:

A: 자기 루프가 없는 모든 꼭짓점
B: 자기 루프를 가지며 다른 모든 꼭짓점과 2개의 간선으로 연결된 꼭짓점
C = V(G)(A∪B), q개의 연결 성분을 가짐

그러면 G는 다음 성질을 만족한다:

A는 독립 집합
C의 각 성분은 완전 그래프 (각 꼭짓점이 자기 루프를 가지고, 임의의 두 꼭짓점 사이에 2개의 간선)
각 성분 Cᵢ와 A 사이의 간선은 홀수 매칭을 구성
2|A| + q = 2|B| + e(A,C) + 2
모든 공집합이 아닌 A' ⊆ A와 C' ⊆ C에 대해: 2|A'| + |C'| ≥ 2 + Σ(e(A', V(Cᵢ)))

기술적 방법

교대 경로 이론

핵심 도구는 Belck-Gallai 교대 경로 이론이다:

교대 경로: 간선이 빨강-파랑으로 교대로 칠해진 중복 없는 간선 경로
꼭짓점 분류: 고정된 시작점 p에서 출발하여, 꼭짓점을 BR-꼭짓점(빨강과 파랑 모두 도달 가능), B-꼭짓점(파랑만 도달 가능), R-꼭짓점(빨강만 도달 가능), 도달 불가능 꼭짓점으로 분류
핵심 보조정리 (정리 2.2): BR-성분은 정확히 1개의 진입 간선을 가짐