1. A graph which edges are ordered pairs of different nodes.

It is a directed graph because the end vertices of an edge are ordered; so, the edges are directed. It can not be a directed pseudograph because every edge joins different nodes.

2. An edge whose endpoints are the same vertex.

It is a loop. It is a particular case of edge and cycle, but we have a special term for it.

3. Consider an edge e=ab of a graph (directed or undirected).
The vertices a and b are ... with the edge e.

The vertices a and b are incident with the edge e. The vertices a and b are adjacent. If the edge is undirected then the vertices a and b are neighbours.

4. A vertex with degree 0.

A vertex with degree 0 is called an isolated vertex. A vertex with degree 1 is called a leaf vertex or an end vertex. A vertex with degree n − 1 in a graph on n vertices is called a dominating vertex.

5. A graph where all vertices are pairwise adjacent.

It is a complete graph. A bipartite graph (bigraph) has two nonintersecting subsets of vertices (parts), and every its edge joins vertices from different parts.There is only one particular case when a complete graph is a complete bipartite graph: it is the graph with two vertices and one edge joining them.

6. A subgraph of a graph G containing all vertices of G.

It is a spanning subgraph. A proper subgraph does not contain all vertices of G. An unduced subgraph can contain any subset of vertices, but all possible adges of the graph G have to ve included in the subgraph.

7. A walk where first and last vertices are the same.

The general term is closed walk. Tour and circuit are closed walks where all edges are different. Cycle is a closed walk where all vertices (except of the stard and the end vertices) are different. So, awalk where first and last vertices are the same is a closed walk.

8. Two graphs that are not distinguished because they have the same structure.

These graphs are isomorphic. Simple and bipartite graphs cah have different structures. Invariant graphs do not exist.

9. An open walk in which all the edges are different.

It is a trail. A tour is a closed walk where all edges are different. A path or a chain is an open walk where all vertices are different; so, every path or chain is a trail, but not vice versa.

10. The number of edges in the walk <u,v>.

It is the length of the walk <u,v>. The distance between u and v is the minimum length of the walk <u,v>. Eccentricity of the vertex u is the minimum distance between the vertex u and other graph vertex. The radius of the graph is the minimum eccentricity of its vertices.

Activity 2: Some facts about graphs

To perform the task, you should know more then terms.

Instruction

Marc correct and incorrect statements.

In a nontrivial simple graph...

TRUE:

the number of odd-degree vertices is even (see Handshaking Lemma);

the sum of all vertex degrees is even (see Handshaking Lemma).

FALSE:

the number of even-degree vertices is even (e.g. any complete graph of an odd order has an odd number of even-degree vertices);

the sum of all vertex degrees can be both even and odd (it can not be odd).

For every bipartite graph having M vertices in one part and N vertices in another part ...

TRUE:

the number of edges does not exceed MN ( a complete bipartite graph has MN edges);

the sum of degrees of the vertices from one part is equal to the sum of degrees of the vertices from another part (any edge joins vertices from different parts).

FALSE:

the sum of degrees is equal to MN (it can be, but not obligatory);

the number of edges is even (it is not so for a complete bigraph where N is even).

The number of non-isomorphic...

TRUE:

The number of non-isomorphic simple graphs of the order 5 is more than 20.

The number of non-isomorphic digraphs of the order 3 is less than 10.

The number of non-isomorphic simple graphs of the order 3 is less then 5.

You can check it by drawing diagramms.

FALSE:

The number of non-isomorphic multigraphs of the order 4 is less than 50 (we can not cilculate the number because en edge can be repeated any number of times).

For a simple graph with N vertices and K connectivity components,

TRUE:

the number of edges is not less than N-K;

the number of edges is not more than N(N-K)/2.

FASLE:

the number of edges is less than N(N-1)/2 ( it can be equal to N(N-1)/2 if K=1);

the number of edges is not less than N(N-K)/2 (it is not more than N(N-k)/2).

A directed graph...

TRUE:

A directed graph is either strongly connected or disconnected.

A directed graph is weakly connected if it is strongly connected.

A directed graph is unilaterally connected if it is weakly connected.

FALSE:

A directed graph is weakly connected if and only if it is unilaterally connected.

A directed graph can be strongly / unilaterally / weakly connected or disconnected. Strong connectiviry implies unilateral connectivity and unilateral connectiviry implies weak connectivity, but not vice versa.

A subgraph...

TRUE:

A subgraph can be both proper and vertex-induced (if it is indused by a part of vertices and includes not all edges).

A subgraph can be either proper or spanning (a spanning subgraph contains all vertices, but a proper subgraph contains not all vertices).

FALSE:

A subgraph can be either proper or vertex-induced.

A subgraph can be either spanning or vertex-induced (spanning vertex-induced subgraph of graph G is G itself).

What is true about walks?

TRUE:

A walk can be either closed or open (the ends of an open walk are different, the ends of a closed walk are the same) .

A path is also a trail (in a path, vertises are not repeated; in a trail, edges are not repeated, but vertices can be came across twice).

A chain does not include cycles.

FALSE:

A tour is also a cycle (vice versa) .

Activity 3: Origin of Graph Theory

Instruction

Watch this video and fill the gaps with the words below. You can use a word more than once.

odd field even trivial two all lines new degree node Geometry graph mathematics Position seven route four degrees path point once mathematician more two

The two islands were connected to each other and to the river banks by seven bridges.

Which route could allow someone to cross all seven bridges without crossing any of them more than once?

Attempting to explain why led famous mathematician Leonhard Euler to invent a new field of mathematics.

Geometry of Position is now known as Graph Theory.

The map could be simplified with each of the four landmasses represented as a single point, what we now call a node, with lines, or edges, between them to represent the bridges.

This simplified graph allows us to easily count the degrees of each node.

The number of bridges touching each landmass visited must be even.

Looking at the graph, it becomes apparent that all four nodes have an odd degree.

A Eulerian path which visits each edge only once is only possible in one of two scenarios.

The first is when there are exactly two nodes of odd degree, meaning all the rest are even.

The second is if all the nodes are of even degree.

The seemingly trivial riddle led to the emergence of a whole new field of mathematics.