Theorem. diameter가 2인 무어 그래프(Moore graph)의 degree는 2,3,7,57만 가능하다.


설명: diameter는 그래프 위에서 가장 먼 두 점 사이의 거리임. girth는 가장 짧은 cycle의 길이.

Diameter가 d일 때 girth의 최댓값(cycle이 없는 tree의 경우는 빼고)을 생각해 보면 2d+1이 가능한 최대임을 쉽게 알 수 있음.(더 긴 사이클에는 diameter땜에 대각선이 있어야하니)

이 등호를 만족하는 연결그래프를 Moore graph라고 함

자명한 예시가 odd cycle이나 complete graph K_n(n은 3이상)이 있음. 

Petersen graph도 예시중 하나. 어떻게생겼는지 궁금하면 구글링 ㄱㄱ


근데 직관좋은사람은 대충 그림 슥슥 그려보면 느낌 올 수도 있겠는데 Moore graph는 항상 regular, 그러니까 모든 vertex의 degree가 같아야만함

그러면 이제 Moore graph는 뭐뭐있느냐 라고 할 수 있겠는데 사실 저기있는게 거의 다임

d=1이면 complete graph인건 당연한 소리고 d>2면 odd cycle밖에 없음이 증명되어있음

그러면 이제 d=2일때의 경우를 봐야 하는데 위에 적힌 정리가 d=2일때의 Moore graph가 finite함을 보여줌(degree, girth가 결정된 Moore graph의 vertex와 edge 갯수는 고정됨)

degree가 2일때는 당연히 cycle이고 degree가 3일때는 Petersen graph뿐이고 degree가 7일때는 Hoffman-singleton graph 라는 애로 유일함이 증명되어있음

그럼 57은? 57일때의 moore graph가 있는지는 아직 미해결임. 있다고 가정하면 이런 저런 성질을 만족한다는 결과들은 있는데 있는지 없는지는 아직 모름


저 정리가 응용성이 개쩌는 정리는 아닌데 증명을 보면 선형대수밖에 안씀. 하드한 선형대수도 아니고 진짜 개론수준? 인접행렬의 eigen value를 냅다 구한다음에 multiplicity를 구해다가 multiplicity가 정수일 조건을 써버리면 바로 됨

그래서 수린이 시절에 보고 굉장히 꽃혔었음. 지금도 가장 좋아함