Mathematics desk
< December 7	<< Nov \| December \| Jan >>	December 9 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 8

Three-way vertex query

As far as I can see by drawing some particular cases, an undirected graph with all vertices being the meet of three edges, and only one edge joining any particular pair of vertices, must have an even number of vertices. Is this the case? Further, how many different such graphs have exactly six vertices? - I can find just two, one with three vertices inside an outside loop of three and the other with two inside an outer loop of four. → 31.50.229.60 (talk) 19:30, 8 December 2017 (UTC)[reply]

For the first statement, see handshaking lemma (and yes, you are correct). For the enumeration of cubic graphs, see [1] (and again you are correct). --JBL (talk) 19:58, 8 December 2017 (UTC)[reply]

Thanks. On checking, my two six-vertex graphs are topologically the same, and the second actual one is invalid for my purposes as it requires edge-crossing. →31.50.229.60 (talk) 13:37, 9 December 2017 (UTC)[reply]

If every vertex belongs to exactly three edges, then 2E = 3V, so not only is V even but E must be a multiple of three. — If you're interested in enumeration of planar graphs, see [2] and [3]; for cubic graphs (those in which each vertex has valence 3), look for the maximum number of vertices for a given number of faces. —Tamfang (talk) 04:26, 13 December 2017 (UTC)[reply]