Selecting the highest-weighted edges in a bipartite graph

Question

This is a real business problem; my apologies if it's trivial or seems like a homework question.

Setup

Consider a fully-connected, bipartite graph $G$ between two vertex sets $V_1$ and $V_2$.

Each vertex set has an associated collection of weights or "scores" $S(V_1)$ and $S(V_2)$ where $S(V_n) = \{s_n(v) : v \in V_n\}$, and $s_n$ is a function mapping $V_n$ to $[0, 1]$.

The edges $E$ also have an associated score that is the product of the scores of the individual vertices; that is, $S(E) = \{s_1(v_1) \cdot s_2(v_2) : (v_1, v_2) \in V_1 \times V_2 \}$.

Question

Consider two particular sub-graphs:

1. ($G1$) The subgraph with the $k$ highest-scoring vertices from $V_1$ and $V_2$.
2. ($G2$) The subgraph with the $k^2$ highest-scoring edges.

Are $G1$ and $G2$ equivalent?

My intuition says that they should be, and I haven't been able to come up with a counterexample. But I'm not sure where to start in proving it.

Ultimately I'm interested in finding the best-scoring graph that contains at most $k$ elements from each of $V_1$ and $V_2$; if there's some "best" way to achieve this goal I'd appreciate pointers in the comments.

Answer 1

I think I have found a counter example for you however I may have misinterpreted part of your question.

Note my $s_n$ uses integers but they could easily be scaled to $[0,1]$

Consider the following graph:

Taking $k=2$ highest weighted vertices from each half gives:

whereas the highest $k^2=4$ edges connects the following: