[대학교이상] 이거 풀어보실 분? 그래프 문제임

[육토리(kjhoon2002)]

꼭짓점 개수가 6 이상인 그래프G 에서,

G와 혹은 그 여그래프 G’ 둘 중 적어도 하나에 길이가 3인 회로가 있다는 걸 보이시오

삼각형 갯수로 어떻게 해보면 되지않을까 라는 느낌은 있는데

더 어떻게 해야할 지 모르겠음..

- dc official App

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[육토리(kjhoon2002)]

f가 머죵?.. 제가 진도를 많이 나간상태는 아니라서 - dc App

[익명(106.252)]

차수가 아니라 경우의수로 나눠야 되네

[익명(211.36)]

Ramsey theory 인가? 개수로 세려몀 더블 카운팅 해야할 듯. - dc App

[익명(110.76)]

vertex 암거나 하나 잡아서 v라 하자. G랑 G complement중 하나에서 v의 deg는 3 이상. 편의상 G에서 deg 3이상이라 하고 nbhd에서 u1, u2, u3를 뽑음. 셋 다 서로 연결 안되어있으면 G complement에서 u1, u2, u3는 삼각형, 하나라도 연결되어있으면 v랑 걔네 둘은 G에서 삼각형

[육토리(kjhoon2002)]

감사합니다 - dc App