4
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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):

graph of a triakis icosahedron

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

two graphs of triakis icosahedra, with external vertices joined in pairs

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.

$\endgroup$
7
  • $\begingroup$ $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. $\endgroup$
    – nickgard
    Commented Jul 29, 2019 at 18:20
  • $\begingroup$ @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 $\endgroup$
    – Hao S
    Commented Jul 29, 2019 at 19:47
  • $\begingroup$ @nickgard: Thanks for pointing out my misunderstanding. I've corrected my answer. $\endgroup$
    – Nick Matteo
    Commented Jul 31, 2019 at 19:34
  • $\begingroup$ @HaoSun: I had misunderstood your question; I've changed my answer to an actual counterexample. $\endgroup$
    – Nick Matteo
    Commented Jul 31, 2019 at 19:36
  • $\begingroup$ I'd misunderstood it too and was just looking for the overall average of a given graph and not every vertex-covering sub-graph. $\endgroup$
    – nickgard
    Commented Aug 1, 2019 at 8:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .