Graphs that every two edges have a common vertex

787 Views Asked by At

Do the following cases enumerate all possible cases when an undirected graph that every two edges have common vertex?

  1. an undirected graph with three vertices, which is also a clique.

  2. an undirected graph with each edge connecting each vertex to a particular vertex, forming a star.

Thanks.

2

There are 2 best solutions below

0
On BEST ANSWER

Suppose that there are more than 1 vertex, $v_1, v_2$, st $deg\, ( v_1), deg \, (v_2) \geq 2 $. Conclude they are connected, and show that there is some triangle imbeded in the graph. Then conclude that any other edge sits on two of the three vertexes of the triangle.

This always assuming that there is some edge in each vertex, and there are no parallel edges.

1
On

There could be isolated vertices.