2
$\begingroup$

Q: http://imgur.com/5EgW0Sa

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

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.