How many graphs with 4 vertices

This means that the number of vertices is odd. Platonic graphs are shown in Figure A Only one, the octahedron, has an Euler tour because it is the only one that is regular with an even degree. None of them have Euler trails. Clearly this applies to every regular graph of odd degree. On the other hand regular graphs with even degree al have Euler tours. Disconnected graphs don't have edges from one component to another.

Hence no Euler tour or Euler trail. Add an edge between the two vertices of odd degree. This may give you a multigraph but that is OK because the Euler Theorems apply to multigraphs. This new graph has an Euler tour because every vertex has even degree. Now remove the added edge and the Euler tour we have just found becomes an Euler trail.

What if a delivery van needs to drop something at every house in every street of a suburb? It would be good to know if the street graph has an Euler tour as then the van's work can be done efficiently. Even an Euler trail would make life easier.

Likewise they all have Hamiltonian paths. Are these conjectures true? Suppose then that it does have a Hamiltonian cycle. Therefore it has to use an even number of the edges 16, 27, 38, 49, 5 10, which we'll call the cross edges.

Assume that 16 and 38 are used. This also leads to a contradiction, but we leave that for you to complete. Unfortunately there is no nice characterisation for Hamiltonian cycles like the Euler Tour Theorem.

In fact even finding a Hamiltonian cycle in a given graph is NP complete which means it's pretty hard to do! There are some valuable results but they are not easy to state. Search the web to see what results are known. Then join two vertices if it is possible for a Knight to move between the corresponding squares. Show that this graph has a Hamiltonian cycle. The adjacency matrix of a complete graph consists of ones except for the main diagonal which is all zeros.

Show that these are necessary and sufficient conditions for a matrix to be an adjacency matrix or find all the necessary and sufficient conditions. The sum of an adjacency matrix with itself has a 2 when the graph has an edge and a zero otherwise. The square of an adjacency matrix tells you something about the number of walks of length two.

What is that? Think of the 9 people as vertices of a graph and join those who know each other. The steps here are to note i that two people must have shaken hands the same number of times, so one of these is the male host; ii one person has to have shaken hands 8 times.

Now remove the two people who have shaken hands the same number of times. Repeat everything above to reduce the number of people under consideration to 4 and so on.

On a countback you'll see that the man and his wife had shaken hands with 4 people. But what is the power here? It's the number of possible edges. To show this note that every edge is used or not used. This is a graph on 20 vertices whose edge set is a union of edges.

So the degrees of all of the vertices are less than 3 and the graph is a disjoint union of even cycles. It is then possible to get an independent set of size Answers to questions Question 1 Unfortunately no. Question 2 Apply the argument of Q1 to show that every land mass, except for the initial and final one, has to be attached to an even number of bridges.

Figure A2: A walk with five bridges How did you go with six bridges? Question 5 Well it just depends on how you deploy your bridges. Question 6 The key point is the even-ness of the number of bridges at each land mass. Question 8 Putting one dot on the page should give a graph with one vertex, so A is not a possibility. Question 9 Because we are not allowing loops, it looks at the start as if there might only be two graphs on two vertices.

Figure A4: Graphs with different looking lines Question 10 After some thought I'd guess that there are two schools of thought. Question 11 There are 11 graphs on 4 vertices. Figure A7: The graph with degree sequence 1, 1, 1, 1, 1, 1 Question 17 Experiment with this. Question 20 The one with each vertex joined to all of the other vertices.

Question 21 No. Figure A8: Three non-isomorphic simple graphs with the same degree sequence Question 22 Yes. Look at the graphs of Q Question 23 Does this have anything to do with the number of edges?

Question 24 This is a repeat of Q. Question 25 The graphs required are shown in Figure A9. Question 27 Question 28 We have put the two complementary pairs together in Figure A Figure A The complementary graphs on three vertices Question 29 If you use the definition of the complement twice on G you get back to G again.

Question 30 There is only one way for the definition to work. It has 30 edges. Question 32 These are just the complements of the graphs in the answer to Q Question 34 We'll list all of the graphs with 0, 1, 2, 3, and 4 edges.

Figure A All the graphs on five vertices with less than or equal to five edges Question 35 On 5 vertices: there are two of them; one with every vertex of degree 2 and the other with degrees of 1, 1, 2, 3, 3. Figure A A graph on eight vertices Question 36 The simple graph on 1 vertex is regular of degree 0.

Question 38 We have shown the regular graphs of degree 2 on 8 vertices in Q21; there are no others. But this is not a whole number. Corollary The number of vertices of odd degree in a graph is even. Proof By the theorem, the sum of the degrees of all of the vertices is even.

Question 41 There are several of these. Figure A Some connected graphs on 6 vertices with 6 edges Question 42 On 3 vertices: the graphs with none and one edge. Question 44 Never. Question 46 On 3 vertices: 1 graph with 2 edges; on 4 vertices: 2 graphs with 3 edges; on 5 vertices: 3 graphs with 4 edges. Conjecture 3 In some graphs there is only one way to go from one given vertex to another given vertex. Conjecture 4 Suppose we have a connected graph.

Check your conjectures out on graphs with 6 vertices to see if they are still true. Question 48 You will have done all sorts of trees. In Figure A14 we give just three. Question 50 This can be done for all connected graphs, but you have to be careful to take off edges that don't disconnect the graph. Question 51 It looks as if they all have at least two vertices of degree 1. Question 52 There are a lot of them Question 53 From Q11, with two components: 3, 4, 7; and with three components: 2. Question 55 Conjecture: They are connected.

Proof: Since trees are connected, then so must be a graph with a tree as a subgraph. Question 57 The answers are shown in Figure A Question 59 There are no cycles in any tree. Question 64 Yes. Just delete an edge of the cycle. For example, any complete graph has a spanning path. Question 65 Yes. Question 66 In Figure 4, the path 1, 2, 3, 4, 5, 10, 8, 6, 9, 7 is one possible spanning path.

Question 67 Yes, there are lots of them. Question 68 Yes, again there are generally lots of them. Question 69 Two! Question 71 2, just alternate the colours as you go from one end of the path to the other.

Question 74 Our original definition assumes that trees are connected and Theorem T1 shows that they are acyclic. Question 75 Can you tell by looking at the sorts of cycles they have? Question 77 Any odd cycle will do. Question 78 Figure A The bipartite graphs with most edges on 3, 4 and 5 vertices. You can verify this yourself by trying to find an Eulerian trail in both graphs.

We now use the above criteria to find some non-planar graphs. K5: K5 has 5 vertices and 10 edges, and thus by Lemma 2 it is not planar. K3,3: K3,3 has 6 vertices and 9 edges, and so we cannot apply Lemma 2. K5 has 5! These can be counted by considering the decomposition of an Eulerian circuit on K5 into cycles. A graph is said to be planar if it can be drawn in a plane so that no edge cross.

Example: The graph shown in fig is planar graph. A region is defined to be an area of the plane that is bounded by edges and cannot be further subdivided. Moreover, since K3,3 is bipartite, it contains no 3-cycles since it contains no odd cycles at all. So each face of the embedding must be bounded by at least 4 edges from K3,3. Moreover, each edge is counted twice among the boundaries for faces. The graph K3,3 is non-planar. K1,k-factorization of complete bipartite graphs Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively.

A K1,k-factorization of Km,n is a set of edge-disjoint K1,k-factors of Km,n which partition the set of edges of Km,n. Given a bipartite graph, testing whether it contains a complete bipartite subgraph Ki,i for a parameter i is an NP-complete problem. A planar graph cannot contain K3,3 as a minor; an outerplanar graph cannot contain K3,2 as a minor These are not sufficient conditions for planarity and outerplanarity, but necessary.

A graph with no loops and no parallel edges is called a simple graph. We see a graph that satisfies the requirements of 8 vertices, 16 edges and all vertices have degree 4 that certainly not planar. So, up to isomorphism, there is only one graph with 6 vertices all with degree 4. Specifically, this graph is the one whose edges and vertices are those of an octahedron. As this graph is not simple hence cannot be isomorphic to any graph you have given.

A vertex a is adjacent to all v i. A pendant edge is attached to a, v 1 , v n. A pendant vertex is attached to b. A pendant vertex is attached to p 1 and to p 2n. The following edges are added: a 1 , b In other words, a i is adjacent to a i-k.. Example: cricket. Example: K 5 - e , K 3,3 -e. Example: C 5. Example: claw , K 1,4 , K 3,3. One endpoint of P is identified with a vertex of C and the other endpoint is identified with a vertex of D. If both C and D are triangles, than P must have at least 2 edges, otherwise P may have length 0 or 1.

Example: house. Example: X Example: triangle , K 4. Example: S 3 , S 4. Example: C 4 , C 6. Example: C 6 , C 8. Example: diamond , gem , 4-fan. Example: triangle , C 5. Example: S 3. Example: paw , 4-pan , 5-pan , 6-pan. The length of the path is the number of edges n Example: star 1,2,2 , star 1,2,3 , fork , claw. The generalisation to an unspecified number of leaves are known as spiders.

Information System on Graph Classes and their Inclusions. Find class. P 5 DhC. K 2,3 D]o. P DKs. C 5 Dhc. X EVzw. H EgSG. H EVjo. X EUrw. P 6 EhCG. P 6 EUzo. W 5 Ehfw. X EUzg. A EhSG. A EUjo. R ElCO. R EQzg. C 6 EhEG. C 6 EUxo.

X 98 EQUO. S 3 Ey[g. X 18 ElCG. X 18 EQzo. X EUyW. X EhGg. X EUvO. X 84 ElD? X 84 EQyw. X 95 EXCW. X 37 EhMG. X 37 EUpo.

X 58 EUwG. X 58 EhFo. K 3,3 -e EFz? X 5 EAxo. X 45 EhQg. X 45 EUlO. X EhTO. X EUig. X EhPo. X EUmG. X EhGw. X EUv? X EhCw. X EUz? X 96 EgTg. X 96 EViO. X EUMW. X FUznw. P 7 FhCGG. P 7 FUzvo. X 85 FhD? C 7 FhCKG. C 7 FUzro. X 12 FKdE? X 12 FrYxw. X 2 FhDOG. X 2 FUyno. X FhDAG. X FUy o. X 11 FKde? X 11 FrYXw. X 20 FhCiG. X 20 FUzTo. X 38 FhCKg. X 38 FUzrO. X 3 FrGX? X 3 FKvew. X 27 FlGHG.