Discrete Mathematics - Graph Theory Question

Pretty confident most of my answers are correct- side from the last one in Q3 iv).

I've done q2 where the last walk was determined to be

For Walks of length i for G2: when i is odd then the counting sequence is 3^(((N+1)^/2) ^-1) , OW 0.

For G3 I've figured out that the # of vertices is a combination of r = 3 and n = i for Gi.

I've drawn all 20 vertices (and their edges) for i) and ii) is 8C3.

My problem is for the last 2 questions. How do I determine adjacency between vertices? Is it the edges that determine this attribute for a vertex?

For g8 - there are 5 new numbers added aside from 1,2 and 3. (4,5,6,7,8) and we want the number of possibilities where order doesn't matter and repetition is not allowed from a pool of 5 numbers for 3 positions. (5c3)

• 456
• 457
• 458
• 468
• 467
• 478
• 578
• 568
• 567
• 678

iv) makes it clear that a triangle is 3 vertexes with an edge between each vertex.

g8 doesn't have 9 unique values and since an edge requires the 3 points to be unique between sets, there will be at most 2 edges between any set of 3 vertices - we want 3.

g9, with its 9 disintct values, can however have triangles. This one I'm still trying to figure out

I tried going about it as such - given (1,2,3) we have 6 values with 6 spots to choose from remaining. The first 3 can be chosen 6C3 ways and the last 3 3C3 ways. So by the rule of product we have (6C3)(3C3) ways of getting a triangle for the point (1,2,3). - Which isn't right because we consider (123)(456)(789) and (123)(789)(456) to be the same triangle. So 6C3 /2.

But then (789)(123)(456), (789)(456)(123) and also (456)(123)(789), (456)(789)(123) are all the same triangle as the one above, just with a different starting vertex.

So for every triangle theres 6 different ways of obtaining it.

if we have 9C3 ways of choosing the first 3 numbers and theres 6 identical triangles for each set of 3 beginning values - then there is a total of 9C3 of choosing unique first values. Each value has 10 different triangles - and the overlap is shared with 6 other combinations of values.

So how many triangles are there? My answer is ( 9C3 * 6C2 / 2 ) / 6

1 Answer

A walk from $b$ to $a$ in $G_2$ must be of the form $bx_1bx_2b\ldots bx_nba$, where each $x_k\in\{a,c,d\}$. For a given $n$ there are $3^n$ such walks, each of length $2n-1$, so

$$w_i'=\begin{cases} 3^{\frac12(i+1)},&\text{if }i\text{ is odd}\\ 0,&\text{if }i\text{ is even}\;; \end{cases}$$

you have a $-1$ exponent in your expression that shouldn’t be there.

Yes, $G_n$ has $\binom{n}3$ vertices, so $G_6$ has $\binom63=20$ vertices, and $G_8$ has $\binom83=56$ vertices.

In any graph two vertices are adjacent if there is an edge between them. Thus, vertices $s$ and $t$ in $G_n$ are adjacent if and only if $s\cap t=\varnothing$. If $s=\{a,b,c\}$ is a vertex of $G_n$, the vertices of $G_n$ adjacent to $s$ are the $3$-element subsets of $\{1,\ldots,n\}$ that are disjoint from $s$, so they are precisely the $3$-element subsets of $\{1,\ldots,n\}\setminus s$. This set has $n-3$ elements, so it has $\binom{n-3}3$ $3$-element subsets. Thus, there are $\binom{n-3}3$ vertices adjacent to any given vertex of $G_n$. (In graph-theoretic terms, $\deg_{G_n}s=\binom{n-3}3$ for each $s\in V_n$.) It appears that in the case $n=8$ and $s=\{1,2,3\}$ you’ve correctly worked all of this out; at any rate your list of the $\binom53=10$ vertices of $G_8$ adjacent to $\{1,2,3\}$ is correct, as is your explanation of it.

Your explanation of why $G_8$ has no triangles is correct. To get a triangle in $G_9$ we must partition $\{1,\ldots,9\}$ into three $3$-element sets, so counting the triangles amounts to counting the partitions of $\{1,\ldots,9\}$ into three $3$-element sets. Suppose that we set out to build such a partition. Exactly one of the three parts must contain $1$; there are $\binom82$ ways to choose the other two elements of this part. Once they’ve been chosen, we single out the smallest unused member of $\{1,\ldots,9\}$ and choose two other unused elements to go into its part; there are $\binom52$ ways to do this. At that point only $3$ elements of $\{1,\ldots,9\}$ haven’t been used, and they form the third part of the partition.

Each partition of $\{1,\ldots,9\}$ into three $3$-element parts can be produced in this way, and none is produced twice, so there are

$$\binom82\binom52=28\cdot10=280$$

such partitions and hence $280$ triangles in $G_9$.