3
$\begingroup$

Define a graph $G$ such that $V(G) = \{2,3,4,5,11,12,13,14\}$ and two vertices $s$ and $t$ are adjacent if and only if $\gcd\{s,t\} = 1$. Draw a diagram of $G$ and find its size $e(G)$.

I can understand V(G) = {2,3,4,5,11,12,13,14} but what are "two vertices $s$ and $t$ are adjacent if and only if $\gcd\{s,t\} = 1$"?

  • 1
    Welcome to the site. Around here it's considered polite to go a step beyond thanking a poster for an answer you liked and to "accept" one of the answers, by clicking on the check mark you'll find to the left of the answer. That will add some reputation points to the poster of your favorite answer.2012-07-22

4 Answers 4

10

A graph is a bunch of dots on your paper, called "vertices". Each dot has a label, which is its name. In your example there are eight dots, named 2, 3, 4, 5, 11, 12, 13, and 14.

Sometimes two vertices are connected by a line, and sometimes they aren't. When two dots are connected, we say they are "adjacent". The line is called an "edge".

This question is asking about a graph where two vertices are connected whenever their labels (which are numbers) have no common divisor bigger than one. For example, vertices 4 and 14 are not connected because the numbers 4 and 14 are both divisible by 2. But vertices 5 and 14 are connected because there is no number bigger than 1 that divides both 5 and 14. We write $\gcd(4, 14)$ for the greatest number, 2, that divides both 4 and 14, and $\gcd(5,14)$ for the greatest number, 1, that divides both 5 and 14.

Your job is to draw all the connections between the dots. You should decide if 2 and 3 are connected, and then draw an edge between them if so. Then decide if 2 and 4 are connected, and so on.

$e(G)$ is just the total number of edges in the graph.

  • 0
    +1 That's a great, simple, clear, elementary explanation!2012-07-22
3

You have $8$ vertices, labelled $2$, $3$, and so on. Now we need to determine the edges.

Look for example at the vertices $2$ and $3$. Are they joined by an edge? They are to be joined precisely if $\gcd(2,3)=1$. The greatest common divisor of $2$ and $3$ is indeed $1$, so draw an edge joining $2$ and $3$.

Are vertices $2$ and $4$ joined by an edge? Well, $\gcd(2,4)=2\ne 1$, so no edge.

Are vertices $2$ and $5$ joined by an edge? Yes, because $\gcd(2,5)=1$. Continue.

Vertex $2$ will be joined to $3$, $5$, $11$, $13$. Now we have produced all the edges that involve $2$.

In addition, $3$ is joined to $4$, $5$, $11$, $13$, $14$.

In addition, $4$ is joined to $5$, $11$, and $13$.

In addition, $5$ is joined to $11$, $12$, $13$, $14$.

In addition, $11$ is joined to $12$, $13$, $14$.

In addition, $12$ is joined to $13$.

And finally, $13$ is joined to $14$.

  • 0
    oh! this was simple!!! thank you!2012-07-22
1

$G=G(V,E)$ is a graph, where $V$ is the set of vertices - in your case the vertices "have names'' or correspond to natural numbers.

Now $E$ is the set of edges, in your case $E:=\{(u,v):gcd(u,v)=1\}$ and by $gcd(u,v)$ I mean the gcd of the natural numbers corresponding to $u,v$.

For example there is an edge between the vertices corresponds to the numbers $1$ and $2$ i.e. $(1,2)\in E$ since $gcd(1,2)=1$ but $(2,4)\not\in E$ since $gcd(2,4)=2\neq1$.

Note:$gcd$ - is the greatest common divisor

0

Here's a drawing of the graph in question.

A drawing of the graph

The $7$ dashed lines represent non-edges, and the $\binom{7}{2}-7=14$ solid lines are the present edges.