1. Given the undirected graph G=(V, E), where V={1,2,3,4,5,6,7}, E={{1,2},{2,3},{3,4},{3,5},{4,5},{5,6},{6,7}}

g=Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]4,3\[UndirectedEdge]5,4\[UndirectedEdge]5,5\[UndirectedEdge]6,6\[UndirectedEdge]7},VertexLabels->"Name"]

a) is the graph simple

SimpleGraphQ[g]

b) is the graph complete ?

gComplete=CompleteGraph[7];
If[g==gComplete,Print["Your graph is complete"],Print["Your graph isn't complete"]]

c) Is the graph connected?

If[Length[ConnectedComponents[g]]==1,Print["Your graph is connected"],Print["Your graph isn't connected"]]

d) Can you find 2 paths from 3 to 6?

HighlightGraph[g,PathGraph[{3,4,5,6}]]
HighlightGraph[g,PathGraph[{3,5,6}]]

e) Can you find a cycle?

HighlightGraph[g,FindCycle[g]]

f) Can you find an edge whose removal makes the graph acyclic?

ed={1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]4,3\[UndirectedEdge]5,4\[UndirectedEdge]5,5\[UndirectedEdge]6,6\[UndirectedEdge]7};
c=Graph[ed];
list={};
list2={};
For[i=1,i≤Length[ed],i++, (*ToDo: improve steps to start from comparison ed then remove 1st element*)
ed1=Drop[ed,{i,i}];
c1=Graph[ed1,VertexLabels->"Name"];
If[AcyclicGraphQ[c1]==True,AppendTo[list,c1]&&AppendTo[list2,ed[[i]]]]
]
list
Print["list of edges to remove: ",list2]

g) Can you find an edge whose removal makes the graph not connected?

edg={1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]4,3\[UndirectedEdge]5,4\[UndirectedEdge]5,5\[UndirectedEdge]6,6\[UndirectedEdge]7};
cg=Graph[edg];
listg={};
list2g={};
For[i=1,i≤Length[edg],i++,(*ToDo: to get as a final answer all edges which could be removed to make graph not connected not only 2 of them*)
ed1g=Drop[edg,{i,i}];
c1g=Graph[ed1g,VertexLabels->"Name"];
If[Length[ConnectedComponents[c1g]]≠ 1,AppendTo[listg,c1g]&&AppendTo[list2g,edg[[i]]]]
]
listg
Print["list of edges to remove: ",list2g]

h) Give the adjacency matrix of G.

AdjacencyMatrix[g]//MatrixForm

i) Is G a tree?

If[TreeGraphQ[g]==True,Print["G is a tree"],Print["G is not a tree"]]

j) Does an Eulerian path exist? (-path of edges)

It doesn’t exist

k) Does a Hamiltonian path exist?(-path of vertices)

HighlightGraph[g,PathGraph[FindHamiltonianPath[g]]]

2. Draw K6, (complete graph with 6 nodes.)

CompleteGraph[6,VertexLabels->"Name", ImageSize->Small]

3. For each of the following characteristics, draw a graph or explain why such graph does not exist:

a) Four nodes of degree 1, 2, 3, and 4, respectively

g3=Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]4,4\[UndirectedEdge]4,4\[UndirectedEdge]3},VertexLabels->"Name"]

b) Four nodes of degree 2, 3, 3, and 4, respectively

g3=Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]3,2\[UndirectedEdge]4,4\[UndirectedEdge]4},VertexLabels->"Name"]

4. If G is a simple graph, the complement of G, denoted G’, is the simple graph with the same set of nodes as G, where nodes x-y are adjacent in G’ if and only if they are not adjacent in G.

a) Draw K4', complement of K4

k=CompleteGraph[4];
k1=GraphComplement[%]

b) Given an adjacency matrix A for a simple graph G, describe the adjacency matrix for G'.

AdjacencyMatrix[k]//MatrixForm
AdjacencyMatrix[k1]//MatrixForm

AdjacencyMatrix[g]//MatrixForm
AdjacencyMatrix[GraphComplement[g]]//MatrixForm

1 replace with 0 and 0 with 1, on the diagonal always zeros.

5. Given the following graph (tree) with node a as the root and constructed from left to right:  T = (V, E), where  V= {a, b, c, d, e, f, g, h, i}, and E ={{a,b},{a,c},{b,d},{b,e},{c,f},{c,g},{d,h}, {d,i}}

t={"a"->"b","a"->"c","b"->"d","b"->"e","c"->"f","c"->"g","d"->"h","d"->"i"};
TreePlot[t,VertexLabeling->True]

a) Is this a binary tree?

TreeGraphQ[Graph[t]]

b) Is it a full binary tree?

Yes: see: http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf

c) Is it a complete binary tree?

No

d) What is the parent of e?

b

e) What is the right child of e?

None

f) What is the depth of g?

2

g) What is the height of the tree?

3

6. Given the following digraph:  D = ( V, E ), where V = { 1, 2, 3, 4, 5} and E = {(1,2),(2,3),(3,4),(4,5),(5,1)}:

d=Graph[{1-> 2,2->3,3->4,4->5,5->1},VertexLabels->"Name",ImageSize->Small]

a) By inspection is the graph strongly connected?

Yes

b) Compute M^2, that is M.M, where M is the adjacency of D.

AdjacencyMatrix[d]//MatrixForm
AdjacencyMatrix[d].AdjacencyMatrix[d]//MatrixForm

c) Compute Warshall's first matrix after the adjacency matrix, 1W.

(Subscript[[  (W^([1])) ] , (i,j)])= 1 if and only if there is a walk from (Subscript[v, i]) to (Subscript[v, j]) with elements of a subset of
{(Subscript[v, 1])} as interior vertices.

listc={{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1},{1,1,0,0,0}}//MatrixForm