. The complete m-partite graph π²ππ,ππ,β¦β¦,ππ has vertices partitioned into m subsets of ππ, ππ, β¦ β¦ , ππ elements each, and vertices are adjacent if and only if they are in different subsets in the partition. For example, if m=2, it is our ever-trusting friend, a complete bipartite graph.
a. Draw these graphs: i. π²π,π,π ii. π²π,π,π iii. π²π,π,π,π
b. How many vertices and how many edges does the complete π²ππ,ππ,β¦β¦,ππ have?
"K_{1,2,3}"
"K_{2,2,3}"
"K_{4,4,5,1}"
the degree of the top of the i-th share
"\\sum\\limits_{i\\neq j}mj"
then
"S=\\sum mj=> \\sum\\limits_{i\\neq j}mj=S-mi"
the sum of the degrees of the vertex of the i-th part
"(S-mi)*mi=Smi-mi^2"
sum of degrees of all vertices
"\\sum Smi-mi^2=S\\sum mi-\\sum mi^2=S^2-\\sum mi^2=(\\sum mi)^2 -\\sum mi^2=\\\\\n=\\sum\\limits_{i<j}2mi*mj"
the number of edges in the graph
"\\frac{1}{2}\\sum\\limits_{i<j}2mi*mj=\\sum\\limits_{i<j}mi*mj"
Comments
Leave a comment