We have already learnt the different types of graphs. Now we are going to learn the properties of these graphs. This section, again, will be full of terminologies to be remembered. Some have quite similar meanings, so take note not to confuse them.

- A
**walk**is an**alternating sequence**of**vertices and edges**of a graph. A**closed walk**is defined to be a walk which starts and ends with the same vertex. - A
**path**is a**sequence of edges**that begins at a vertex of a graph and travels from vertex to vertex along the edges of the graph. A**simple path**is then a path which doesn’t contain the same edge more than once. The**length**of a path is the amount of edges that the path contains. - A
**trail**is a walk that has**no repeated edges**. In some cases when the word trail is used, a path could mean a walk that has no repeated vertices. Take note of the double meaning of the word path. - A
**circuit**is a path that begins and ends at the same vertex in an**undirected graph**. A**simple circuit**is then a circuit with not repeated edges. - A
**cycle**is a path that begins and ends at the same vertex in a**directed graph**. - The
**degree sequence**is the listing down of all the vertices not by its name, but by its degree of vertex. It is listed in**non-increasing**(which means, decreasing lah…) order.

To illustrate these 5 terms, I will show you an example below:

* You can construct many walks in this graph. An example of a walk here is **(v _{1}, e_{1}, v_{2}, e_{6}, v_{3}, e_{7}, v_{4})**. Remember that a walk starts and ends with a vertex.

* An example of a path is **e _{1}, e_{6}, e**

_{7 }or

**e**, which both have length 3.

_{2}, e_{5}, e_{7}* A trail can be just as the walk above, **(v _{1}, e_{1}, v_{2}, e_{6}, v_{3}, e_{7}, v_{4})**, as long as there are no repeated edges.

* A circuit here, can be something like **e _{1}, e_{6}, e_{5}, e_{2} **or

**e**It will be called as a cycle if it were a directed graph. Note that you can only follow the directions of the arrow for a cycle.

_{3}, e_{6},e_{2}.* The degree sequence for **v _{1}, v_{2}, v_{3}, v_{4 }**is

**6, 4, 3, 1**. Remember that the sum of the degree of vertex should be an even number.

__CONNECTEDNESS__

A graph is **connected** when there’s a path between every pair of distinct vertices of the graph. This means that, if I start walking from any vertex, I am able to reach any other vertex by traversing the edges (by the way, you **pass through **a vertex, but **traverse **an edge).

In the case of a directed graph, we say that it is **strongly connected **when there is a path **a **→** b** and **b** → **a** whenever **a** and **b** are vertices of the graph. And then, it is **weakly connected **when there is at least a path **a** →** b** or **b** → **a **for any vertex **a **and **b** in the graph. Or in other words, a weakly connected graph exists if there is a path between every 2 vertices in the underlying undirected graph.

A **connected component **is just a connected subgraph. For example, the graph

has 3 connected components. We can further say that a component is a **strongly connected component** / **strong component **if a component is the maximal strongly connected subgraph.

**Cut vertices (articulation points)** are vertices whose removal and all the edges incident with it produces more connected components than the original graph.

**Cut edges (articulation bridges)** are edges whose removal produces a graph with more connected components than in the original graph.

__ISOMORPHIC GRAPHS__

We say that 2 graphs are **isomorphic** if:

1. They have **equal vertices** and **edges**, **degree sequence **and **length of simple circuits**

(these properties are known as the **graph invariants**).

2. Follow paths that go through all vertices so that the corresponding vertices of the 2 graphs

have the same degree.

For example, the graphs below:

You notice something? **A** and **R** are isomorphic graphs. Also, **F** and **T**, **K** and **X**, and **M, S, V** and **Z** are isomorphic graphs. It is easy to identify isomorphic graphs for small amount of vertices, but remember to use the above rule if the graphs are really complicated.

__EULERIAN TRAILS & CIRCUITS__

The town of **K****ӧ****nigsberg, Prussia **was divided into 4 sections by the branches of the **Pregel River**. These 4 sections included the 2 regions on the banks of the Pregel (**A** & **B**), Kneiphof Island (**C**), and the region between the 2 branches of the Pregel (**D**). In the 18th century, 7 bridges connected these regions.

On Sundays, the residents take long walks through the town. They wondered whether it was possible to start at some location in the town, travel across every bridge without crossing any bridge twice and return to the starting point. Do you want to try and see whether you can find a simple circuit for them?

We’ll come back later. An **Eulerian Trail** (or **Euler Path**) is a simple trail that contains **every edge** in the graph, while an **Eulerian Circuit** (or **Euler Circuit**) is a simple circuit containing every edge in the graph. For example,

An Euler Circuit in the graph is **e _{3}, e_{1}, e_{2}, e_{6}, e_{7}, e_{5}, e_{4}, e_{9}, e_{10}, e_{8}**. Take note that an Euler path doesn’t necessarily return to the same vertex, but an Euler circuit has to. By the way, the word ‘Euler’ is read as ‘Oil-lerr’, not ‘you-lerr’.

It is found that there is a condition for these Eulerian properties to exist:

An Eulerian trail exists in a graph if there are

exactly2 vertices withodd degrees.

An Eulerian circuit only exists ifevery vertexin a graph haseven degrees.

Take a look at the graph above, you will see that every vertex has degree 4. That explains why an Eulerian circuit exist.

Now, let’s rephrase our previous question. So are we able to find an ‘Eulerian circuit’ for the **Kӧ****nigsberg **bridge? First, we draw the bridges as edges, the river banks and islands as vertices. We get a graph like this:

Counting the degree of vertices, we find that these 4 vertices have odd degrees. Therefore, we can conclude that it is impossible to cross all 7 bridges, and come back to the same spot, neither is it possible to cross all the bridge once in any order. Although we didn’t find a solution, we proved that a solution can’t found.

__HAMILTONIAN PATHS & CYCLES__

Just now we did for edges, now we do the same for vertices. A **Hamiltonian path **(or **Hamilton path**)** **is a simple path in a graph that passes through every vertex exactly once, whereas a **Hamiltonian cycle **(or **Hamilton circuit**) is a simple cycle in a graph that passes through every vertex exactly once. Look at the graph below:

The red lines shows a Hamiltonian cycle. Note that the word cycle here might not necessarily mean that it has to be a directed graph. A Hamiltonian path, doesn’t need to start and end at the same vertex.

Surprisingly, there is no known simple necessary and sufficient criteria for the existence of Hamiltonian cycles. However, there are 2 theorems over here which might possibly work. I don’t think this is examinable:

**1.** **Dirac’s Theorem**: The graph G has a Hamiltonian cycle if the degree of every vertex is at least half of the number of vertices. **n**, with **n ≥ 3**.

Note that this theorem doesn’t say anything about graphs whose degree of every vertex less than half of the number of vertices. It might, and might not have a Hamilton path, and you have to check it through.

**2. Ore’s Theorem:** The graph G with **n **vertices has a Hamiltonian cycle if for every non-adjacent pairs of vertices **u **and **v**, **deg (u) + deg (v) ≥ n**.

I believe Hamiltonian cycle questions in STPM won’t be too hard, so don’t worry too much about it for now. Questions on Euler and Hamilton paths and circuits will involve identifying them, or focusing on what you can do to make an Euler or Hamilton circuit exist.

__OTHER EXTRA INFORMATION__

These are probably out of the syllabus, but I treat it as extra information for you:

**1. Planar Graphs**A planar graph is a graph that can be drawn in the plane without any edges crossing. In this case, a

**region**is the area bounded by a circuit in the graph. There are quite a few corollaries for planar graphs, for example,

* If G is a connected planar simple graph, then G has a vertex of degree not exceeding 5.

* If G is a connected planar simple graph with **e** edges and **v** vertices, where **v ≥ 3**, then **3v – 6 ≥ e* **If a connected planar simple graph has

**e**edges and

**v**vertices with

**v ≥ 3**, and has no circuits of length three, then

**2v – 4 ≥ e**.

*

**Kuratowski’s Theorem**states that a graph is nonplanar iff it contains a subgraph homeomorphic to K

_{3,3}or K

_{5}. 2 graphs are

**homeomorphic**if they can be obtained from the same graph by a sequence of

**elementary subdivision**, which is the action of putting a vertex in the middle of an edge.

The **crossing number **is the minimum number of crossings that can occur when a graph is drawn in plane where no 3 edges are permitted to cross at the same point. The **thickness **of the graph is the smallest number of planar subgraphs of G than have G as their union.

**2. Euler’s Formula **For a connected planar simple graph, The amount of regons can be represented by the equation

**r = e – v + 2**.

**3. Chromatic Number**

We define the chromatic number **χ(G)** to be the least number of colours needed for a colouring of a graph. **Colouring** is defined to be the assignment of a colour to each vertex of the graph so that no 2 adjacent vertices are assigned the same colour. Recall what you learnt about bipartite graphs in the previous section. **The Four Colour Theorem **states that the chromatic number is always less than 4 for a planar graph. We say that a graph is **chromatically k-critical** if the chromatic number of G is k, but for every edge e, the chromatic number is k – 1 by deleting this edge from G.

We could modify the definition of colouring to describe edges too. **Edge colouring** is an assignment of colours to edges so that edges incident with a common vertex are assigned different colours. The **edge chromatic number** is the smallest number of colours that can be used in an edge colouring in a graph. The edge chromatic number can actually be found by finding the biggest number of degree of vertex in the graph.

**4. Vertex Basis**A vertex basis is a set of vertices where there’s a path to every vertex outside this set from vertices of this set, and there’s no path from any vertex in the set to another vertex in the set. In other words, any vertex in a directed graph, which only points outwards but not inwards, is belongs to a vertex basis.

Other than the last part of this section, please put some effort in reading them. Graph Theory is easy, so make sure you score it. ☺

From the notes above is it mean that a hamiltonian cycle is also known as hamilton circuit?

ReplyDeleteYes. Remember the definition cycle is for a directed graph, circuit for undirected. However, the terminologies differ from text books, so as long as you see the word Haimiltonian, you know what it is.

ReplyDeleteI remembered how my teacher taught me ,a parabola which opens up has a lowest point and a parabola which opens down has a highest point and the highest or lowest point on a parabola is called the vertex.

ReplyDeletedefinition of a function