# how many vertices does this graph have.....

• January 22nd 2007, 11:27 PM
m777
how many vertices does this graph have.....
Hello,
plz try to solve this question.

QUESTION:
Suppose that a connected planer simple graph has 25 edges. If a plane drawing of this graph has 10 faces, how many vertices does this graph have?
• January 23rd 2007, 03:28 AM
CaptainBlack
Quote:

Originally Posted by m777
Hello,
plz try to solve this question.

QUESTION:
Suppose that a connected planer simple graph has 25 edges. If a plane drawing of this graph has 10 faces, how many vertices does this graph have?

Such a graph satisfies Euler's Polyhedron formula:

n-m+f=2

where n is the number of vertices, m the number of edges, and f the
number of faces. So:

n=2+25-10=17.

RonL
• January 23rd 2007, 07:42 AM
anthmoo
Quote:

Originally Posted by CaptainBlack
Such a graph satisfies Euler's Polyhedron formula:

n-m+f=2

where n is the number of vertices, m the number of edges, and f the
number of faces. So:

n=2+25-10=17.

RonL

Is this just pretty much the same as Euler's Relationship:

R + N = A + 2 ?
• January 23rd 2007, 07:46 AM
ThePerfectHacker
Quote:

Originally Posted by anthmoo
Is this just pretty much the same as Euler's Relationship:

R + N = A + 2 ?

I am not sure what you are saying but there is:
1)Euler Formula for Planar Graphs.
2)Euler Formula for Polyhedra.
These two formulas are the same.
#1 is stronger than #2.
Because I believe one way of proving #2 is from #1.
• October 27th 2008, 06:30 PM
wik_chick88
Quote:

Originally Posted by CaptainBlack
Such a graph satisfies Euler's Polyhedron formula:

n-m+f=2

where n is the number of vertices, m the number of edges, and f the
number of faces. So:

n=2+25-10=17.

RonL

is there a way of finding the number of faces (or regions as its called in our classnotes) from just looking at a graph? eg. how many faces/regions does $K_{3,3}$ have?