The edge parity of the 4n vertex subgraphs of a 4n+1 vertex graph

30 Views Asked by At

Is this true? If so why? In EVERY 4n+1 vertex graph: if EVERY vertex has an EVEN order then: ALL the 4n+1 subgraphs of size 4n have either an odd number of edges or an even number of edges.

1

There are 1 best solutions below

0
On

Yes, if in any finite graph $G$ all vertices $v$ have even degree $\deg v$ then the parity of number of edges $|E(G-v)|$ in each induced subgraph $G-v$ is the same as the parity of number of edges $|E(G)|$ of the graph $G$, because $|E(G-v)|=|E(G)|-\deg v$.