An unlabeled graph may have an arbitrary number of vertices with none, one, or more edges connecting some or all of the vertices. A graph may have several separate (not connected) subgraphs in the system.

   The chart above shows a graph containing 10 vertices and 11 edges. Four of the vertices are connected by 3 edges to form a tree. 5 more vertices are connected by 8 edges to form another subgraph that has multiple cycles. (You can travel along some (or all) the edges and return to your starting point.) Finally, vertices do not have to be connected to anything.

   In any generalized graph system containing "V" vertices, there are potentially COMBIN(V, 2) edges that could be drawn. If we select any "E" of these for our graph, then there are COMBIN(COMBIN(V, 2), E) potential graph systems that could be drawn. A difficult problem in combinatorics is to calculate how many of these are structurally different.

   The table below shows all combinations up to 13 vertices. (If anyone would like results to larger numbers of vertices, I can attach an Excel Spreadsheet to an E-mail.)

   A typical row in the table translates as follows. If you have 2 edges and only 2 vertices, no graph is possible. If you have 2 edges and 3 vertices, 1 graph is possible. (Start at any vertex, draw the first edge to another vertex, and draw the 2nd edge to the remaining vertex. With 4 or more vertices, 2 structurally different graphs are possible. Each of the edges could connect a separate pair of vertices, or the edges could form a chain leaving one (or more) vertices unused.

   At the end of the table I have included an outline on how to calculate these results. However, a full description of the process would require many pages explaining "Why" various calculations are being made.


    
 
 

Number
of                   <----------   Number of Vertices     ----------->
Edges  2 3 4 5  6   7     8      9        10          11             12                13
-----------------------------------------------------------------------------------------
   0   1 1 1 1  1   1     1      1         1           1              1                 1
   1   1 1 1 1  1   1     1      1         1           1              1                 1
   2   0 1 2 2  2   2     2      2         2           2              2                 2
   3   0 1 3 4  5   5     5      5         5           5              5                 5
   4   0 0 2 6  9  10    11     11        11          11             11                11
   5   0 0 1 6 15  21    24     25        26          26             26                26
   6   0 0 1 6 21  41    56     63        66          67             68                68
   7   0 0 0 4 24  65   115    148       165         172            175               176
   8   0 0 0 2 24  97   221    345       428         467            485               492
   9   0 0 0 1 21 131   402    771     1,103       1,305          1,405             1,446
  10   0 0 0 1 15 148   663  1,637     2,769       3,664          4,191             4,435
  11   0 0 0 0  9 148   980  3,252     6,759      10,250         12,763            14,140
  12   0 0 0 0  5 131 1,312  5,995    15,772      28,259         39,243            46,415
  13   0 0 0 0  2  97 1,557 10,120    34,663      75,415        119,890           154,658
  14   0 0 0 0  1  65 1,646 15,615    71,318     192,788        359,307           517,121
  15   0 0 0 0  1  41 1,557 21,933   136,433     467,807      1,043,774         1,711,908
  16   0 0 0 0  0  21 1,312 27,987   241,577   1,069,890      2,911,086         5,546,619
  17   0 0 0 0  0  10   980 32,403   395,166   2,295,898      7,739,601        17,422,984
  18   0 0 0 0  0   5   663 34,040   596,191   4,609,179     19,515,361        52,664,857
  19   0 0 0 0  0   2   402 32,403   828,728   8,640,134     46,505,609       152,339,952
  20   0 0 0 0  0   1   221 27,987 1,061,159  15,108,047    104,504,341       420,048,805
  21   0 0 0 0  0   1   115 21,933 1,251,389  24,630,887    221,147,351     1,101,083,128
  22   0 0 0 0  0   0    56 15,615 1,358,852  37,433,760    440,393,606     2,739,261,020
  23   0 0 0 0  0   0    24 10,120 1,358,852  53,037,356    825,075,506     6,461,056,816
  24   0 0 0 0  0   0    11  5,995 1,251,389  70,065,437  1,454,265,734    14,441,470,390
  25   0 0 0 0  0   0     5  3,252 1,061,159  86,318,670  2,411,961,516    30,583,652,956
  26   0 0 0 0  0   0     2  1,637   828,728  99,187,806  3,765,262,970    61,372,294,334
  27   0 0 0 0  0   0     1    771   596,191 106,321,628  5,534,255,092   116,724,411,757
  28   0 0 0 0  0   0     1    345   395,166 106,321,628  7,661,345,277   210,474,287,115
  29   0 0 0 0  0   0     0    148   241,577  99,187,806  9,992,340,187   359,954,668,522
  30   0 0 0 0  0   0     0     63   136,433  86,318,670 12,281,841,209   584,089,835,857
  31   0 0 0 0  0   0     0     25    71,318  70,065,437 14,229,503,560   899,632,282,299
  32   0 0 0 0  0   0     0     11    34,663  53,037,356 15,542,350,436 1,315,729,343,451
  33   0 0 0 0  0   0     0      5    15,772  37,433,760 16,006,173,014 1,827,823,498,798
  34   0 0 0 0  0   0     0      2     6,759  24,630,887 15,542,350,436 2,412,694,353,115
  35   0 0 0 0  0   0     0      1     2,769  15,108,047 14,229,503,560 3,026,821,673,656
  36   0 0 0 0  0   0     0      1     1,103   8,640,134 12,281,841,209 3,609,810,088,490
  37   0 0 0 0  0   0     0      0       428   4,609,179  9,992,340,187 4,093,273,437,761
  38   0 0 0 0  0   0     0      0       165   2,295,898  7,661,345,277 4,413,678,080,790
  39   0 0 0 0  0   0     0      0        66   1,069,890  5,534,255,092 4,525,920,859,198
  40   0 0 0 0  0   0     0      0        26     467,807  3,765,262,970 4,413,678,080,790
  41   0 0 0 0  0   0     0      0        11     192,788  2,411,961,516 4,093,273,437,761
  42   0 0 0 0  0   0     0      0         5      75,415  1,454,265,734 3,609,810,088,490
  43   0 0 0 0  0   0     0      0         2      28,259    825,075,506 3,026,821,673,656
  44   0 0 0 0  0   0     0      0         1      10,250    440,393,606 2,412,694,353,115
  45   0 0 0 0  0   0     0      0         1       3,664    221,147,351 1,827,823,498,798
  46   0 0 0 0  0   0     0      0         0       1,305    104,504,341 1,315,729,343,451
  47   0 0 0 0  0   0     0      0         0         467     46,505,609   899,632,282,299
  48   0 0 0 0  0   0     0      0         0         172     19,515,361   584,089,835,857
  49   0 0 0 0  0   0     0      0         0          67      7,739,601   359,954,668,522
  50   0 0 0 0  0   0     0      0         0          26      2,911,086   210,474,287,115
  51   0 0 0 0  0   0     0      0         0          11      1,043,774   116,724,411,757
  52   0 0 0 0  0   0     0      0         0           5        359,307    61,372,294,334
  53   0 0 0 0  0   0     0      0         0           2        119,890    30,583,652,956
  54   0 0 0 0  0   0     0      0         0           1         39,243    14,441,470,390
  55   0 0 0 0  0   0     0      0         0           1         12,763     6,461,056,816
  56   0 0 0 0  0   0     0      0         0           0          4,191     2,739,261,020
  57   0 0 0 0  0   0     0      0         0           0          1,405     1,101,083,128
  58   0 0 0 0  0   0     0      0         0           0            485       420,048,805
  59   0 0 0 0  0   0     0      0         0           0            175       152,339,952
  60   0 0 0 0  0   0     0      0         0           0             68        52,664,857
  61   0 0 0 0  0   0     0      0         0           0             26        17,422,984
  62   0 0 0 0  0   0     0      0         0           0             11         5,546,619
  63   0 0 0 0  0   0     0      0         0           0              5         1,711,908
  64   0 0 0 0  0   0     0      0         0           0              2           517,121
  65   0 0 0 0  0   0     0      0         0           0              1           154,658
  66   0 0 0 0  0   0     0      0         0           0              1            46,415
  67   0 0 0 0  0   0     0      0         0           0              0            14,140
  68   0 0 0 0  0   0     0      0         0           0              0             4,435
  69   0 0 0 0  0   0     0      0         0           0              0             1,446
  70   0 0 0 0  0   0     0      0         0           0              0               492
  71   0 0 0 0  0   0     0      0         0           0              0               176
  72   0 0 0 0  0   0     0      0         0           0              0                68
  73   0 0 0 0  0   0     0      0         0           0              0                26
  74   0 0 0 0  0   0     0      0         0           0              0                11
  75   0 0 0 0  0   0     0      0         0           0              0                 5
  76   0 0 0 0  0   0     0      0         0           0              0                 2
  77   0 0 0 0  0   0     0      0         0           0              0                 1
  78   0 0 0 0  0   0     0      0         0           0              0                 1
-----------------------------------------------------------------------------------------
Totals 2 4  34  1,044      274,668         1,018,997,864               50,502,031,367,952
          11  156    12,346       12,005,168            165,091,172,592


   Calculations are a "little" involved. First, for each column (Number of Vertices) you have to generate the "Cycle Index Formula for the Symmetric Groups". The Cycle Index Formula for 5 vertices is shown below. (The web editor leaves a "little" to be desired for subscripts and superscripts, but I hope you get the idea.)


        1   5       3       2         2                        ("1 over" & Superscripts)
Z(S ) = --(s   + 10s s + 20s s + 15s s + 30s s + 20s s + 24s ) (Main line)
   5    5!  1       1 2     1 3     1 2     1 4     2 3     5  (FACT(5) & Subscripts)


(Note: In this and the following equation, if no superscript (power) is shown, it is an implied "1".) The first term is "1" divided by FACT(Nbr. of Vertices). The terms inside the parenthesis are derived from the way 5 objects can be partitioned. (Five 1's, three 1's and one 2, two 1's and one 3, one 1 and two 2's, one 1 and one 4, one 2 and one 3, one 5.) The coefficient for each term inside the parenthesis is calculated by starting with 5! = 120. Then for each "s" in each term, first divide by FACT(Superscript). Then divide again by Subscript^Superscript.

   Next we have to convert the "Cycle Index Formula for the Symmetric Groups" (above) to the "Cycle Index Formula for the Pair Groups". For our 5-vertex equation this becomes:

   (2)    1   10      4 3        3      2 4        2                 2
Z(S   ) = --(s   + 10s s  + 20s s  + 15s s  + 30s s  + 20s s s  + 24s )
    5     5!  1       1 2      1 3      1 2      2 4      1 3 6      5

   The conversion for each of the terms inside the parenthesis (in our 5 vertex example there are 7 terms) is calculated as follows: For each "s" in each term let "k" equal the old subscript and "JsubK" equal the old superscript. Then if "k" is odd, the new subscript simply copies "k". The new superscript becomes: (JsubK)*[((k)(JsubK)-1)/2]. (Note: If the superscript goes to "0", the "s" disappears.)

   If "k" is even, then the single "s" expands into 2 "s" components. For the first of these, the superscript remains the same while the subscript is divided by 2. For the second "s" the subscript remains the same while the new superscript becomes: (JsubK)*[((k)(JsubK)-2)/2)]. (Note: Again, if the superscript goes to "0", the "s" disappears.)

   Finally, for each of the (old) terms that have two or more "s" components, then for each possible pair of s's, we generate a new "s" where the new subscript is the least common multiple of the subscripts of the two s's in the pair, and the superscript equals: the product of the two superscripts and multiplied again by the greatest common divisor of the two superscripts.

   As an example of how these calculations work, let's work with the second term in the first equation. The first "s" has an odd subscript. Thus, the old subscript "1" stays at "1". The new superscript becomes: 3[((1)(3)-1)/2] = 3.

   The second "s" is even, thus we will have two resulting "s" terms. The first of these keeps the old superscript of "1" while the subscript gets cut in half to "1". The second "s" term will keep the old subscript of "2" and the new superscript becomes: 1[(2)(1)-2)/2] = 0. (This "s" will thus disappear.)

   Finally, there are 2 "s" terms in the first equation. Thus will have to apply the pair rule once. The subscript will be:
LCM(1, 2) = 2. The superscript for the new "s" will be: (3)(1)[GCD(3, 1)] = 3.

Combining these three operations yields:

                       3   1   0   3          4   3
Converted term = (10)(s )(s )(s )(s ) = (10)(s )(s )
                       1   1   2   2          1   2

   When we combine and simplify these new terms we get the "Cycle Index Formula for the Pair Groups". If all you want to know is the total number of structurally different graphs (without a breakdown by specific number of edges), you can use the "Pair" equation.

   For example, if your graph is confined to 2 "colors" (either an edge exists or it doesn't), simply substitute "2" for each "s" in the "Pair" equation. (This will give you the grand total shown at the bottom of the table.) If you want 3 "colors" (e. g. No edge, green edge, or black edge), substitute a "3" instead.

For the 5 vertex "Pair" equation, if we substitute "2" for "s" it becomes:

Total combinations = 1/5! [2^10 + 10(2^4)(2^3) + 20(2)(2^3) + 15(2^2)(2^4) + 30(2)(2^2) + 20(2)(2)(2) + 24(2^2)] = 34


   If you want the complete Edge/Vertex table, another step is required. To get the results shown in the table: substitute "1 + Y" for each "s" and then use the subscripts and superscripts to perform the following polynomial multiplication: ((1 + Y^(Subscript))^Superscript). Then add the polynomials for each term. For example: The second term in the "Pair" formula becomes:  10[((1 + Y^1)^4) + ((1 + Y^2)^3)].

After you have combined all the terms for the Number of Vertices = 5 formula you will get:

(1/5!) * [ 120 + 120Y + 240Y^2 + 480Y^3 + 720Y^4 + 720Y^5 + 720Y^6 + 480Y^7 + 240Y^8 + 120Y^9 + 120Y^10]

which reduces to the values in the table.


Return to Durango Bill's Home Page



Web page generated via Kompozer