Question 1 (10 marks) Let G= (V, E), where V is a set of nodes {v1, vz, ..., Vn) and E is a set of edges { {vi, vi), where vi, V E V ), be an undirected graph. Recall that an undirected graph is connected if there is a path from any node in the graph to any other node in the graph. (Graphs do not have to be connected !) Definition: An undirected graph G has property P if and only if it is possible to divide all its nodes into two disjoint sets such that all its edges have one endpoint in each set. Note that there is no requirement for the graph to be connected in order to have property P Example of a graph that has property P. V3 Graph G1 Example of a graph that does not have property P V2 Graph G2 1.1 Consider the 4 nodes in the picture below. Draw all undirected graphs that have only those 4 nodes as vertices and also have property P. 1.2 Prove that a graph that has property P cannot contain a cycle whose length is an odd number. (Note: theoretical results like this one are very useful in practice because they can often aid in the design of efficient of algorithms for checking whether a given graph has a property of interest. These types of results are most useful when brute force algorithms for directly checking the property of interest are difficult to implement or very inefficient.)