MathDB

Graph theory

Source: 12th XMO

April 13, 2023

graph theoryxmocombinatorics

Problem Statement

求最小的

n,

使得对任意有

{1000}

个顶点且每个顶点度均为

{4}

的简单图

G,

都一定可以从中取掉

{n}

条边

,

使

{G}

变为二部图

.