A certain graph is 19 vertices 19 edges and no circuits Is i

A certain graph is 19 vertices, 19 edges, and no circuits. Is it connected? Explain.

Solution

Consider the bi-partition graph G(V,E) where V is partitioned into two distinct vertex subsets, labelled with odd and even numbers |{1,3,5,7,9,11,13,15,17,19}|=10 and |{2,4,6,8,10,12,14,16,18}|=9. Then, the edge set E, that connects the graph is a paring of k with k+1, and k+1 with k, i.e. 1=2,2=3, ..., k-2=k-1,k-1=k. Furthermore, this is a minimum edge set connecting G. It consists of 18 edges connecting 19 vertices adding a vertex and edge at each k>1

Any additional edge, e, (the required 19th edge), that connects any of the existing vertices of G, creates a circuit. So the graph G, is connected but has a circuit.

Consider removing any vertex of the connected bi-partite graph with a circuit, This is a disconnected graph, however, then one removes a vertex and removes 2 or 3 edges (depending on the chosen vertex). The Graph G, can\'t be disconnected and left with 19 edges and no circuits.