Return to Question

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} $$ is at most linear in the number of vertices.

What I know about this problem:

• This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
• I can prove an upper bound of $O(n \log(n))$ as follows. Let $A_i = \{v : 2^i \leq deg(v) < 2^{i+1}\}$, and let $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Now, $E(G)$ is the union of the $E_i$'s, and the contribution of an edge from $E_i$ is at most $2^{i+1}$. On the other hand, as $G$ is planar the size of $E_i$ is at most $3|\cup_{j \geq i} A_i |$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $2^i$ is at most $6n/2^i$. Therefore $|E_i| \leq 18 n/ 2^i$. We have $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} \leq \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(deg(x),deg(y))} $$ $$ \leq\sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq \sum_{i=0}^{\log_2(n)} (18 n/ 2^i) \cdot 2^{i+1} = 36 n \log_2(n). $$

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(\deg(x),\deg(y))} $$ is at most linear in the number of vertices.

What I know about this problem:

• This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
• I can prove an upper bound of $O(n \log(n))$ as follows. Let $A_i = \{v : 2^i \leq \deg(v) < 2^{i+1}\}$, and let $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Now, $E(G)$ is the union of the $E_i$'s, and the contribution of an edge from $E_i$ is at most $2^{i+1}$. On the other hand, as $G$ is planar the size of $E_i$ is at most $3|\cup_{j \geq i} A_i |$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $2^i$ is at most $6n/2^i$. Therefore $|E_i| \leq 18 n/ 2^i$. We have $$ \sum_{\{x,y\} \in E(G)}{\min(\deg(x),\deg(y))} \leq \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(\deg(x),\deg(y))} $$ $$ \leq\sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq \sum_{i=0}^{\log_2(n)} (18 n/ 2^i) \cdot 2^{i+1} = 36 n \log_2(n). $$

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} $$ is at most linear in the number of vertices.

What I know about this problem:

• This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
• I can prove an upper bound of $O(n \log(n))$ as follows. Let $A_i = \{v : 2^i \leq deg(v) < 2^{i+1}\}$, and let $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Now, $E(G)$ is the union of the $E_i$'s, and the contribution of an edge from $E_i$ is at most $2^{i+1}$. On the other hand, as $G$ is planar the size of $E_i$ is at most $3|\cup_{j \geq i} A_i |$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $2^i$ is at most $6n/2^i$. Therefore $|E_i| \leq 18 n/ 2^i$. We have $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} \leq $$ $$ \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(deg(x),deg(y))} \leq $$ $$ \sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq $$ $$ \sum_{i=0}^{\log_2(n)} (18 n/ 2^i) \cdot 2^{i+1} = 36 n \log_2(n). $$

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} $$ is at most linear in the number of vertices.

What I know about this problem:

• This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
• I can prove an upper bound of $O(n \log(n))$ as follows. Let $A_i = \{v : 2^i \leq deg(v) < 2^{i+1}\}$, and let $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Now, $E(G)$ is the union of the $E_i$'s, and the contribution of an edge from $E_i$ is at most $2^{i+1}$. On the other hand, as $G$ is planar the size of $E_i$ is at most $3|\cup_{j \geq i} A_i |$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $2^i$ is at most $6n/2^i$. Therefore $|E_i| \leq 18 n/ 2^i$. We have $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} \leq \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(deg(x),deg(y))} $$ $$ \leq\sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq \sum_{i=0}^{\log_2(n)} (18 n/ 2^i) \cdot 2^{i+1} = 36 n \log_2(n). $$

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} $$ is at most linear in the number of vertices.

What I know about this problem:

• This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
• I can prove an upper bound of $O(n \log(n))$ as follows. Let $A_i = \{v : 2^i \leq deg(v) < 2^{i+1}\}$, and let $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Now, $E(G)$ is the union of the $E_i$'s, and the contribution of an edge from $E_i$ is at most $2^{i+1}$. On the other hand, as $G$ is planar the size of $E_i$ is at most $3|\cup_{j \geq i} A_i |$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $2^i$ is at most $6n/2^i$. Therefore $|E_i| \leq 18 n/ 2^i$. We have $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} \leq $$ $$ \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(deg(x),deg(y))} \leq $$ $$ \sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq 32 n \log_2(n). $$

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} $$ is at most linear in the number of vertices.

What I know about this problem:

• This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
• I can prove an upper bound of $O(n \log(n))$ as follows. Let $A_i = \{v : 2^i \leq deg(v) < 2^{i+1}\}$, and let $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Now, $E(G)$ is the union of the $E_i$'s, and the contribution of an edge from $E_i$ is at most $2^{i+1}$. On the other hand, as $G$ is planar the size of $E_i$ is at most $3|\cup_{j \geq i} A_i |$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $2^i$ is at most $6n/2^i$. Therefore $|E_i| \leq 18 n/ 2^i$. We have $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} \leq $$ $$ \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(deg(x),deg(y))} \leq $$ $$ \sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq $$ $$ \sum_{i=0}^{\log_2(n)} (18 n/ 2^i) \cdot 2^{i+1} = 36 n \log_2(n). $$