# Testing if a Graph is Balanced

The "average degree" of a graph $G = (V,E)$ is $$\frac{2|E|}{|V|}$$ or simply $2l/k$, i.e. twice the number of edges divided by the number of vertices.

With $H$ a graph, if we simply write $d(H)=2l/k$, we can then look at the maximum of $d$ of over subgraphs of H, i.e. with $m(H)$ the maximum average degree of a graph $H$, $$m(H)=\max\{d(F):F \subset H\}$$

A graph $H$ is balanced if the graph itself has an average degree equal or larger than the average degrees of all its subgraphs, i.e. $m(H)=d(H)$.

It is strictly balanced when the average degree of $H$ is strictly larger than all of its subgraphs. See Chapter 4 of B. Bollobás "Random Graphs" 2001.

Trees, cycles and complete graphs are always strictly balanced. See the examples of Bollobás below.

Is there a quick way to test whether a graph is strictly balanced? I am currently doing this by taking subsets of all its vertices, forming the induced subgraphs $F_1,F_2,\dots$ of each via Subgraph, then finding $d(F_1),d(F_2),\dots$ and comparing it to $m(H)$ until it is clear when the graph itself has strictly largest average degree, using

AvDegree[x_] := N[2*Length[EdgeList[x]]/Length[VertexList[x]]]


but for a large dataset, this takes too long.

• Simple examples of each type of graph would be helpful. – Carl Woll Jan 5 '18 at 16:46
• I have added those given by Bollobás. – apkg Jan 5 '18 at 16:58
• What sizes of graphs are you interested in? – Carl Woll Jan 5 '18 at 18:36
• Quite small, say no bigger than 100 nodes – apkg Jan 6 '18 at 17:45
• But this can get costly if I then repeat 100,000 times – apkg Jan 6 '18 at 17:46

Here is one slow possibility. You can cast the problem as a linear programming problem, with a vector consisting of indicator variables for the edges and vertices. Let the vector be: $(e_1, .., e_m, v_1, .., v_n)$ where there are $m = |E_G|$ edges and $n = |V_G|$ vertices in the graph. Then the graph has $d_G = 2 |E_G| / |V_G|$. Now, a subgraph $H$ will have $d_H = 2 |E_H| / |V_H|$. Then, we have:

$$|E_G| |V_H| - |E_H| |V_G| = d_G |V_G| |V_H|/2 -d_H |V_G| |V_H|/2 = (|V_G| |V_H|/2) ( d_G - d_H)$$

The sign of the minimum over all subgraphs $H$ of $|E_G| |V_H| - |E_H| |V_G|$ will determine whether the graph is unbalanced, balanced or strictly balanced.

The LinearProgramming constraints come from each vertex in the graph: if the vertex is not in the subgraph, then the associated edges must be absent from the subgraph. Here is the function:

balanceQ[g_] := Module[
{e=EdgeList[g], ec=EdgeCount[g], v=VertexList[g], vc=VertexCount[g], res},

res = Quiet[
LinearProgramming[
Join[
-vc Table[1, {ec}],
ec Table[1, {vc}]
],
Join[
Table[
With[{b = Boole[Not@*FreeQ[v[[i]]] /@ e]},
],
{i, vc}
],
{
Join[Table[0, {ec}], Table[1, {vc}]],
Join[Table[0, {ec}], Table[1, {vc}]]
}
],
Join[
Table[{0, -1}, {vc}],
{
{1, 1}, (* at least one vertex *)
{vc-1,-1} (* not all vertices *)
}
],
Table[{0, 1}, {vc+ec}],
Integers
],
LinearProgramming::lpip
];
Switch[Sign[-vc Total[res[[;;ec]]] + ec Total[res[[ec+1;;]]]],
-1, "Unbalanced",
0, "Balanced",
1, "Strictly balanced"
]
]


As an example, consider graphs from GraphData:

g = GraphData /@ GraphData[30];

SortBy[AbsoluteTiming[balanceQ[#]]& /@ g, First]


{{0.001414, "Balanced"}, {0.002054, "Unbalanced"}, {0.002168, "Unbalanced"}, {0.002208, "Balanced"}, {0.024167, "Unbalanced"}, {0.043445, "Unbalanced"}, {0.049372, "Strictly balanced"}, {0.069279, "Balanced"}, {0.083165, "Strictly balanced"}, {0.086195, "Strictly balanced"}, {0.094856, "Strictly balanced"}, {0.100238, "Balanced"}, {0.103429, "Strictly balanced"}, {0.110622, "Strictly balanced"}, {0.123556, "Strictly balanced"}, {0.133809, "Strictly balanced"}, {0.138439, "Strictly balanced"}, {0.157034, "Strictly balanced"}, {0.195019, "Strictly balanced"}, {0.226968, "Strictly balanced"}, {0.237197, "Strictly balanced"}, {0.267112, "Strictly balanced"}, {0.267291, "Strictly balanced"}, {0.322829, "Strictly balanced"}, {0.327068, "Strictly balanced"}, {0.333683, "Strictly balanced"}, {0.344322, "Strictly balanced"}, {0.352541, "Strictly balanced"}, {0.373047, "Strictly balanced"}, {0.384115, "Strictly balanced"}, {0.411243, "Strictly balanced"}, {0.423324, "Strictly balanced"}, {0.433958, "Strictly balanced"}, {0.443956, "Strictly balanced"}, {0.448159, "Strictly balanced"}, {0.460425, "Strictly balanced"}, {0.47054, "Strictly balanced"}, {0.479184, "Strictly balanced"}, {0.485696, "Strictly balanced"}, {0.502723, "Strictly balanced"}, {0.51482, "Strictly balanced"}, {0.528539, "Strictly balanced"}, {0.536904, "Strictly balanced"}, {0.538585, "Strictly balanced"}, {0.546364, "Strictly balanced"}, {0.55003, "Strictly balanced"}, {0.614187, "Balanced"}, {0.709653, "Strictly balanced"}, {0.710389, "Unbalanced"}, {0.742609, "Strictly balanced"}, {0.781095, "Strictly balanced"}, {0.885017, "Strictly balanced"}, {0.925772, "Strictly balanced"}, {1.1346, "Strictly balanced"}, {1.21853, "Strictly balanced"}, {1.30096, "Balanced"}, {1.32248, "Strictly balanced"}, {1.3259, "Strictly balanced"}, {1.33169, "Strictly balanced"}, {1.49999, "Strictly balanced"}, {1.77298, "Strictly balanced"}, {2.14196, "Strictly balanced"}, {2.19037, "Strictly balanced"}, {2.26871, "Strictly balanced"}, {2.33642, "Strictly balanced"}, {2.49905, "Strictly balanced"}, {2.58194, "Strictly balanced"}, {2.58368, "Strictly balanced"}, {2.70069, "Strictly balanced"}, {2.86718, "Strictly balanced"}, {2.86911, "Strictly balanced"}, {2.87815, "Strictly balanced"}, {2.90138, "Strictly balanced"}, {3.24567, "Strictly balanced"}, {3.4512, "Strictly balanced"}, {4.92757, "Strictly balanced"}, {4.95015, "Strictly balanced"}, {4.9556, "Strictly balanced"}, {5.0526, "Strictly balanced"}, {5.05777, "Strictly balanced"}, {5.25303, "Strictly balanced"}, {5.51572, "Strictly balanced"}, {5.93311, "Strictly balanced"}, {7.65476, "Strictly balanced"}, {8.4197, "Strictly balanced"}, {9.07264, "Strictly balanced"}, {9.89535, "Strictly balanced"}, {10.352, "Strictly balanced"}, {11.3917, "Strictly balanced"}, {151.473, "Strictly balanced"}, {215.75, "Strictly balanced"}}

Even for graphs with 30 vertices, the timing for balanceQ ranges from .001 to 215, so it is very slow, but should be much faster than checking $|E_H|/|V_H|$ for all 2^30 subgraphs.

• Thank you, I’ll run this and give you some feedback. – apkg Jan 7 '18 at 14:21
• Yes this is ideal, it is able to list which graphs are balanced, strictly balanced, or unbalanced very quickly. – apkg Nov 6 '19 at 6:55