China
Africa
Explore chapters and articles related to this topic
Network Analysis
Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018
Michael W. Carter, Camille C. Price, Ghaith Rabadi
A graph is a bipartite graph if the nodes can be partitioned into two subsets S and T, such that each node is in exactly one of the subsets, and every arc in the graph connects a node in set S with a node in set T. Such a graph is a complete bipartite graph if each node in S is connected to every node in T. The graph in Figure 3.2 is a complete bipartite graph in which nodes A and B are in one subset, and nodes C, D, and E are in the other.
Proof levels of graph theory students under the lens of the Van Hiele model
Published in International Journal of Mathematical Education in Science and Technology, 2022
Antonio González, Víctor Manero, Alberto Arnal-Bailera, María Luz Puertas
The fourth item provides some hints to proof the statement of the preceding item. Thus, if this scaffolding does not work as a deterrent for students that use visual arguments, then they are assigned level 1. Level 2 expected answers, just like in item 3, lie in specific verifications in examples, in contrast with level 3 answers, which provide mathematical reasoning beyond examples. This item does not allow to assess level 4 of proof since students have enough information to construct the required proof just by properly relating the claims provided in the statement of the item. Item 5. Here you have a proof of the fact that no complete bipartite graph with an odd number of vertices is Eulerian. Read it and try to understand it:The vertex set of the complete bipartite graph is partitioned into two sets, one having n vertices and the other having m vertices. Each vertex of a set is adjacent to all the vertices of the other set, and there are no adjacencies among vertices of the same set. (See Figure 2).Thus, the vertices of one set have degree m and the vertices of the other set have degree n.As the total number of vertices is n + m, which is an odd number, then either m is odd, and n is even or vice versa.Therefore, the graph has vertices of odd degree and so it is not Eulerian.You have just seen a proof of the fact that no complete bipartite graph with an odd number of vertices is Eulerian. Give a similar proof for the following statement: A complete bipartite graph Kn,m is Eulerian if and only if n and m are both even.