Question

离散数学证明题: 设连通图G有k个奇数度的结点，证明在图G中至少要添加k/2条边才能使其成为欧拉图．

Answer 1

图G是欧拉图的充要条件是图G连通且所有的结点的度数都是偶数，因此要使连通图G成为欧拉图，既是要使所有的结点度数变为偶数。
添加一条边后，可能会出现两种情况：
1、边的两端连接在同一个结点上（环），此时该点的度数加2，奇偶性不变；
2、边的两端连接在两个不同的结点上，此时此两点的度数各加1，两个点改变奇偶性。
如题，图G有k个奇度数的结点，要使该图成为欧拉图，需要改变这k个结点的奇偶性，因此最少需要添加k/2条边。