Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$"?

share|improve this question
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. –  Rick Decker Jul 22 '12 at 20:06

4 Answers 4

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.

share|improve this answer
Thank you! it was simple! –  Intellectual_ Jul 22 '12 at 19:23
I'm glad I could help. –  MJD Jul 22 '12 at 21:07
+1 That's a great, simple, clear, elementary explanation! –  M Turgeon Jul 22 '12 at 21:20

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

share|improve this answer
oh! this was simple!!! thank you! –  Intellectual_ Jul 22 '12 at 19:00

$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

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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