Problem 33A. Let $\tau(G)$ denote the number of spanning trees in a graph $G$ (this is sometimes called the complexity of $G$ ). Show that for any nonloop $e \in E(G), \tau(G)=\tau\left(G_{e}^{\prime}\right)+\tau\left(G_{e}^{\prime \prime}\right)$
PProblem 33B. Find the chromatic polynomial of the $n$-gon $C_{n}$. Find the chromatic polynomial of the $n$-wheel $W_{n}$ (this is the graph obtained from $C_{n}$ by adding a new vertex and joining it to all vertices of $C_{n}$ ).
先用递推确定Cn的染色多项式然后确定Wn的
Problem 33E. Determine all pairs $\left(d_{1}, d_{2}\right)$ of integers with $d_{i} \geq 2$ $i=1,2$, so that there exists a planar graph (not necessarily simple) that is regular of degree $d_{1}$ and such that all faces have degree $d_{2}$.
用欧拉公式加上穷举法
ProbleProblem 33E. Determine all pairs $\left(d_{1}, d_{2}\right)$ of integers with $d_{i} \geq 2$ $i=1,2$, so that there The torus is the surface of a doughnut. Instead of drawing on a plane, one can try to draw graphs on a torus. Draw the complete bipartite graph $K_{4,4}$ on the torus with no edges intersecting (except at the vertices).
直接用多边形表示画一下
MATH 239Introduction to Combinatorics78%likedEasy26%Useful85%85 comments450 ratingsIntroduction to graph theory: colourings, matchings, connectivity, planarity. Introduction to combinatorial analysis: generating series, recurrence relations, binary strings, plane trees. [Note: Offered: F,W,S]Course ScheduleWinter 2022Fall 2021Spring 2021Winter 2021SectionClassEnrolledTimeDateLocationInstructorLEC 0016074302/31512:00 AM – 12:00 AMMTWThFSSuOnlineLEC 0026075233/30012:00 AM – 12:00 AMMTWThFSSuOnlineLEC 00361970/60LEC 00465700/60LEC 00570220/60LEC 00661950/60LEC 08165710/400TUT 1011096251/521:30 PM – 2:20 PMMTWThFSSuOnlineTUT 1021096346/528:30 AM – 9:20 AMMTWThFSSuOnlineTUT 1031096451/528:30 AM – 9:20 AMMTWThFSSuOnlineTUT 1041096555/526:30 PM – 7:20 PMMTWThFSSuOnlineTUT 1051096648/529:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1061096751/5211:30 AM – 12:20 PMMTWThFSSuOnlineTUT 1071096827/509:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1081096940/509:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1091097033/509:30 AM – 10:20 AMMTWThFSSuOnlineTUT 1101097150/501:30 PM – 2:20 PMMTWThFSSuOnlineTUT 1111097250/501:30 PM – 2:20 PMMTWThFSSuOnlineTUT 1121097333/501:30 PM – 2:20 PMMTWThFSSuOnlineLast updated 2 hours ago from classes.uwaterloo.ca
