Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: Daniel Bastos <dbastos@toledo.com>
Newsgroups: alt.algebra.help,comp.programming
Subject: on notation, MM', graph theory, incidence matrix product
Date: Sat, 16 Sep 2017 11:26:57 -0300
Organization: Aioe.org NNTP Server
Lines: 15
Message-ID: <86k20y90su.fsf@toledo.com>
NNTP-Posting-Host: BA7GfgzDJAJU6NkcC5s5CQ.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain
X-Complaints-To: abuse@aioe.org
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
X-Notice: Filtered by postfilter v. 0.8.2
Cancel-Lock: sha1:d67rcj0dFbdaABBrtgnTzomtWyc=
Xref: csiph.com alt.algebra.help:4993 comp.programming:8006

Problem.  Show that if G is simple, the entries on the diagonals of both
MM' and A^2 are the degrees of the vertices of G.

I don't understand what is meant by MM'.  M is the incidence matrix of
graph G.  By looking at section 1.4, subgraphs, I take that M' must be
the incidence matrix of some subgraph induced by M, but M is a matrix,
so I'm puzzled.  AFAIK, I need a set of vertices of a set of edges to
induce a subgraph.

I appreciate a clarification on the book's notation.  Thank you!

This is problem 1.5.2 in ``Graph theory with applications'' by
J.A. Bondy and U.S.R. Murty, Department of Combinatorics and
Optimization, University of Waterloo, Ontario, Canada.  North-Holland,
fifth printing, 1982.  ISBN: 0-444-19451-7.