Math Is Fun Forum

freddogtgj

Member

Registered: 2006-12-02

Posts: 54

Algorithmic Graph Theory Help

Consider the graph G defined as follows.  The vertex set V(G) consists of all triples

with each

equal to 0 or 1.  The edge set E(G) consists of all pairs of triples

such that there is exactly one number i with

≠

.

How many vertices does G have? How many edges does G have?

Thanks in advance!
Sorry for the maths looking like superscript compared to the rest of the text.  Anyone like to tell me how to deal with that will also be great.

Last edited by freddogtgj (2009-01-12 01:42:52)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Algorithmic Graph Theory Help

What part of the problem are you having trouble with?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

freddogtgj

Member

Registered: 2006-12-02

Posts: 54

Re: Algorithmic Graph Theory Help

Well, the stumbling block for me is the vertex part.  I'm not quite sure how the vertex points are meant to be read.  It says that the set consists of all triples with each x_i equal to 0 or 1, but i thought that a vertex can only be defined by one x_i rather than a triple.  Am i wrong?

mathsmypassion

Member

Registered: 2008-12-01

Posts: 33

Re: Algorithmic Graph Theory Help

You are working in 3D. So the coordinate system has three axes.
Because 2×2×2 = 8 you have 8 vertices in V(G).

000,001,011,010,100,110,101,111

Using the definition of the edge, for example 000, 111 does not represent one because thre are 3 different numbers between them not 1 as required but 000 , 001 is an edge.
There are a few others, try to find them.

freddogtgj

Member

Registered: 2006-12-02

Posts: 54

Re: Algorithmic Graph Theory Help

Ok i see mathsmypassion.  Now does that mean the number of edges are 12?

mathsmypassion

Member

Registered: 2008-12-01

Posts: 33

Re: Algorithmic Graph Theory Help

12 sounds good for me.