Thread: Planar graphs. Hint please :)

Is there a connected planar (simple) graph such that:
(a) each vertex has degree 4?

Havn't done decision maths in a while and googles not much help.(or maybe im not looking very well!)

Just need a hint really if you can. .

Im tempted to say there is not...but im not sure if im meant to use an algorithm or some equation to show such...

Thank-yous

Hint: Recall bipartite graphs, where you have two sets of verticies X and Y, where the verticies of X are only connected to vertices of Y and vice-versa. Which values of X and Y would you choose such that each vertex has degree 4?

sadly, don't think there's an algorithm to always find such graphs. however, the Handshaking Lemma can be useful for showing that some graphs can't exist. (if the sum of the degrees of each vertex is an odd number... what can we conclude?)

Originally Posted by MacstersUndead

Hint: Recall bipartite graphs, where you have two sets of verticies X and Y, where the verticies of X are only connected to vertices of Y and vice-versa. Which values of X and Y would you choose such that each vertex has degree 4?

sadly, don't think there's an algorithm to always find such graphs. however, the Handshaking Lemma can be useful for showing that some graphs can't exist. (if the sum of the degrees of each vertex is an odd number... what can we conclude?)

Thankyou for your reply

The thing i was thinking about handshaking lemma though - we don't know how many nodes there are (i could have misread something though, forgive me)

There could be 5 vertices (each connected to each other). Like a star.

Or with a bipartite graph, there could be k(4, 4)...which would mean there would be 8 vertices?

Neither planar.

But there could be more i'm not thinking of, and one possibly being planar...

EDIT: I think im thinking of a different hand shaking lemma, and not the one specific for planar graph. Going to have a read through that one .

Oh! I didn't see the word 'planar'. That changes the question completely. You're right, neither K5 or K4,4 can be planar (Kuratowski's Theorem). I'm sorry I can't help more.

I wonder if you could use brute force and show that these are the only two graphs which every vertex having degree 4 on the plane. If you do so, then you have shown there is no connected simple planar graph with that condition.

EDIT: i was thinking what you were thinking for the Handshaking Lemma. my mistake.

Originally Posted by AshleyCS

Is there a connected planar (simple) graph such that:
(a) each vertex has degree 4?

Originally Posted by Plato

How did you manage to come up with that!?

Apart from you blatently being a genious

Was there a particular method you used? Or just messed around with the vertices?

Thanks

Originally Posted by AshleyCS

How did you manage to come up with that!?
Was there a particular method you used? Or just messed around with the vertices?

Forty years of experience.