2
$\begingroup$

Given a complete symmetric graph $G(V,E)$ with real-valued edgeweights and assume that every induced $k_4$ that is induced by a quadruplet from $v$'s vertices has a unique perfect matching of maximal weightsum and, whose edges have different weights.

Question:
if from $E$ all edges are removed that resemble the heavier edge of the heaviest perfect matching of the $K_4\subseteq G$, is the resulting graph planar?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Probably not. Let V have six vertices, and put small weights on a K3,3 subgraph and large weights on the rest of the edges. I suspect there is a weighting that will leave the nonplanar digraph after removing the heavy edges. Gerhard "Weighted Graphs Can Be Tricky" Paseman, 2020.04.17. $\endgroup$
    – Gerhard Paseman
    Commented Apr 17, 2020 at 14:19
  • $\begingroup$ @GerhardPaseman are you trying to enforce a violation of one of Kuratowski's criteria for the planarity of graphs? $K_{3,3}$ is a Moebius ladder graph and thus locally planar, but not globally by virtue of the twist. At least a clever idea for a possible counter example. $\endgroup$
    – Manfred Weis
    Commented Apr 17, 2020 at 14:39
  • $\begingroup$ I'm suggesting an idea for how to construct a variety of examples. Let some sufficiently complicated graph class be called C. Make your post as above, but replace planar by C. I'm suggesting a counterexample by picking a graph outside of C, putting small weights on the edges, and large weights on the complementary edges. Gerhard "Trying To Throw Off Balance" Paseman, 2020.04.17. $\endgroup$
    – Gerhard Paseman
    Commented Apr 17, 2020 at 14:53

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .