MathCastle
Graph TheoryEasyEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Easy problem

In K3,3K_{3,3} (66 vertices), take two vertices u,vu,v from the same side, so they are not adjacent. Ore's theorem asks whether deg⁡(u)+deg⁡(v)≥n\deg(u)+\deg(v)\ge n. What is deg⁡(u)+deg⁡(v)\deg(u)+\deg(v)?