图论，用蓝白线段为边染色，求证白边端点分属两部分，蓝边端点都在一部分中

abababa

平面上有$n$个点，将这些点分别用蓝、白线段连结，若所得图的任意闭路上都有偶数条白边，求证能将$n$个点分为两个集合$X,Y$，使得$X\cap Y=\varnothing$，每条白边的端点分别在$X,Y$中，每条蓝边的端点或者都在$X$中或者都在$Y$中。

Czhang271828

不妨假定图是连通的. 若不连通, 对有限个连通分支分别简单归纳就行.

任取 $v\in \text{顶点集}$. 定义顶点集到二元集的函数
$$
\phi:\text{顶点集}\to \{\color{red}{\text{奇数}},\color{red}{\text{偶数}}\},\quad u\mapsto \color{red}{\text{x}},
$$
使得 $u$ 到 $v$ 的某一条路经由$\color{red}{\text{x}}$条白边.

往后说明 $\phi$ 是良定义的, 也就是 $\phi(u)$ 与路的选取无关. 任取两条 $u$ 到 $v$ 的路, 依照任意闭路上都有偶数条白边, 往后显然.

abababa

Czhang271828 发表于 2024-8-10 16:10
不妨假定图是连通的. 若不连通, 对有限个连通分支分别简单归纳就行.

任取 $v\in \text{顶点集}$. 定义顶 ...

设$u,v$间的任意两条路径为$p_1,p_2$，则因为$uvu$本身是一个闭路，所以在$p_1,p_2$合并起来构成的图中，必定只有一些闭路和一些$p_1,p_2$的公共边，闭路上的白边是偶数，公共边被计数两次，白边数量也是偶数，所以$p_1,p_2$上的白边总数是偶数，所以$\phi(u)$定义良好。

后面怎么证明呢？应该是将点分成$X=\{x:\text{路径$v,x$上有偶数条白边}\},Y=\{x:\text{路径$v,x$上有奇数条白边}\}$。这样$X\cap Y=\varnothing$，然后怎么证明每条白边的端点分别在$X,Y$中，每条蓝边的端点或者都在$X$中或者都在$Y$中呢？

Czhang271828

abababa 发表于 2024-8-10 19:01
设$u,v$间的任意两条路径为$p_1,p_2$，则因为$uvu$本身是一个闭路，所以在$p_1,p_2$合并起来构成的图中， ...

以下证明任意白边的端点 $\phi$-值相异. 任取 $x\xrightarrow{\text{白}}y$, 那么 $\phi(x)$ 通过某条路 $v\overset{P}{\to \cdots \to } x$ 定义, 而 $\phi(y)$ 可以通过路 $v\overset{P}{\to \cdots \to } x\xrightarrow{\text{白}}y$ 定义. 此时 $x\xrightarrow{\text{白}}y$ 是跨越 $X$ 与 $Y$ 的一条边.

abababa

Czhang271828 发表于 2024-8-12 21:10
以下证明任意白边的端点 $\phi$-值相异. 任取 $x\xrightarrow{\text{白}}y$, 那么 $\phi(x)$ 通过某条路  ...

原来如此，得用上那个定义，谢谢。