A circuit is a closed walk with at least one edge, with no repeated edges. A graph G has
a Euler circuit if it is connected, and if every vertex in said graph has an even positive
integer degree.
The graph here is not
...
A circuit is a closed walk with at least one edge, with no repeated edges. A graph G has
a Euler circuit if it is connected, and if every vertex in said graph has an even positive
integer degree.
The graph here is not a Euler circuit because it does not fit the first criteria of being
connected, and the second of having every vertex with an even positive integer degree.
Vertices v4 and v5, for example, each have a degree of 3; thus, this graph is not a Euler
circuit.
Can there be a simple graph that has n vertices all of different degrees? Why or why
not?
A simple graph is a graph with a simple circuit, and a simple circuit is a circuit (which is
a closed walk with at least one edge and no repeating edges) with no repeated vertices
besides the first and last vertex (which is the same since it is a circuit).
Then suppose graph G is a simple circuit with all different degrees; then that means
that for every vertex there must be a degree of n>1.
So if graph G has 4 vertices, then the degrees must be n1=1, n2=2, n3=3, n4=4.
But following the definition of simple circuit, n1 cannot be 1 because it must have at
least n≥2 because it needs to connect to a different vertex to complete the circuit.
Since there are only 4 vertices, there cannot be a degree of 5, so that n1 must have a
degree of at least two but less than 4, which means it will share a degree with either
n2, or n3, or n4, thus proving that all the degrees cannot be different. Which shows
that for a simple graph with n vertices, all the vertices cannot have differing degrees for
the graph to remain simple.
A large pile of coins consists of pennies, nickels, dimes, and quarters.
If the pile contains only 6 quarters but at least 20 of each other kind of coin, how many
collections of 20 coins can be chosen?
Here, need to select 20 coins out of a set of 4 (pennies, nickels, dimes, and quarters),
with at most 6 of the 20 being quarters:
calculating the overall number of selecting 20 coins out of a set of 4:
C(20+4-1, 20) = C(23, 20) = C(23, 3) = 23!/(23!(23-20)!)
Then suppose all 6 quarters were selected out of the 20 coins, then:
6!/20!
And then the remaining 14 coins were selected from the other 3 coins, so that:
C(14+3-1, 14) = C(16,14) = C(16, 2) = 16!/(16!(16-14)!)
So that by the inclusion/exclusion principle, finding the selection of 20 coins out of a
set of 4 with at most 6 being quarters equals to the overall number of selectionsselecting all 6 – selecting for the remaining set of 3:
How many distinguishable orderings of the letters of MILLIMICRON begin with M and
end with N?
Here, there are 11 letters, but if M and N are already in place, then need to select the
order of the 9 remaining letters (set of 9);
3 I
2 L
1 M
1 C
1 R
1 O
so the possible orderings are:
9! / (3!*2!*1!*1!*1!*1!)
Answer the following questions -
a) According to the Inclusion/Exclusion Rule for Two Sets
"If A and B are finite sets, then N(A ∪ B) = N(A) + N(B) − N(A ∩ B)"
Now, how many integers from 1 through 100 are neither multiples of 3 nor multiples of
4?
b) Let S = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Suppose six integers are chosen from S. Must
there be two integers whose sum is 15? Why?
a. according to the pigeonhole principle- k/n
so A= 100/3 = 33 and B= 100/4 = 25
and (A ∩ B) is 4*3 = 12 ; then by k/n: 100/12=
so that the number of integers from 1 through 100 are neither multiples of 3 nor
multiples of 4 is equal to:
100 – 33 – 25 – 100/12
b. partition the set into 5 subsets:
{3,12}
{4, 11}
{5, 10}
{6, 9}
{7, 8}
where each subset’s sum is equal to 15. Then choosing any 3 of the above subsets (six
numbers), will guarantee that at least two numbers will equal to 15; similarly, if
choosing 5 of the smallest numbers from the above subsets (3,4,5,6,7) then choosing
the 6th to be the smallest of the second pairs (8), 7+8 will equal 15, hence out of any 6
integers chosen, at least 2 pairs will sum up to 15
[Show More]