MathCastle
Graph TheoryChallengePlanar Graphs

Planar Graphs · Challenge problem

Let X={a,b,c}X=\{a,b,c\} and Y={x,y,z}Y=\{x,y,z\}. Build a graph GG with all 66 cross edges of K3,3K_{3,3} EXCEPT axax, byby, czcz, together with 33 new relay vertices p,q,rp,q,r and the paths a-p-xa\text{-}p\text{-}x, b-q-yb\text{-}q\text{-}y, c-r-zc\text{-}r\text{-}z in their place. By how much does the bipartite edge bound 2V−42V-4 EXCEED GG's actual edge count EE?