# Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 13?

Loosely related to Every simple planar graph with $\delta\geq 3$ has an adjacent pair with $deg(u)+deg(v)\leq 13$ Since the proof is a kinda averaging argument, I wonder if one can get more than the existence of just one such edge. What is the smallest number that 13 can be replaced with so that the statement is true?

No.

Consider the counterexample to the linked question, the graph of a triakis icosahedron. This is a planar graph with 60 triangular faces, 12 vertices of degree 10, 20 vertices of degree 3, 60 edges of weight 13, and 30 edges of weight 20. It's possible to choose a cover from among the edges of weight 13, so this in itself isn't a counterexample.

Here is a planar drawing within an external triangle (from MathWorld):

Now take two copies of this and join the external vertices, like so:

Now every edge has weight at least 13, but any edge involving any of the six external vertices of the two triangles has weight at least 14. So any collection of edges covering every vertex must have average weight strictly greater than 13.

• $13$ spokes isn't enough. That gives $13$ edges (the rim) with weight $6$ and $13$ edges (the spokes) with weight $16$, so the average is only $11$. It's not a problem though. The average will go up by $0.5$ for each extra spoke, so $17$ spokes has an average of $(17\times 6+17\times 20)/17=13$, and $18$ spokes gets the average to $13.5$, disproving the conjecture. Commented Jul 29, 2019 at 18:20
• @nickgard note I said average degree 13 so take the border of the wheel along with a single spoke which averages to less than 13 Commented Jul 29, 2019 at 19:47
• @nickgard: Thanks for pointing out my misunderstanding. I've corrected my answer. Commented Jul 31, 2019 at 19:34
• @HaoSun: I had misunderstood your question; I've changed my answer to an actual counterexample. Commented Jul 31, 2019 at 19:36
• I'd misunderstood it too and was just looking for the overall average of a given graph and not every vertex-covering sub-graph. Commented Aug 1, 2019 at 8:02