Matrix Theorem (Kirkhoff) Clarification
$begingroup$
I know that if you take the determinant of the Laplacian Matrix, then you can get the number of spanning trees. However is that also the case for when you have either the Adjacency Matrix or the Degree Matrix?
If not, what would you have to do to find the amount of spanning trees if you were only provided the adjacency matrix (or degree matrix)?
graph-theory
$endgroup$
add a comment |
$begingroup$
I know that if you take the determinant of the Laplacian Matrix, then you can get the number of spanning trees. However is that also the case for when you have either the Adjacency Matrix or the Degree Matrix?
If not, what would you have to do to find the amount of spanning trees if you were only provided the adjacency matrix (or degree matrix)?
graph-theory
$endgroup$
add a comment |
$begingroup$
I know that if you take the determinant of the Laplacian Matrix, then you can get the number of spanning trees. However is that also the case for when you have either the Adjacency Matrix or the Degree Matrix?
If not, what would you have to do to find the amount of spanning trees if you were only provided the adjacency matrix (or degree matrix)?
graph-theory
$endgroup$
I know that if you take the determinant of the Laplacian Matrix, then you can get the number of spanning trees. However is that also the case for when you have either the Adjacency Matrix or the Degree Matrix?
If not, what would you have to do to find the amount of spanning trees if you were only provided the adjacency matrix (or degree matrix)?
graph-theory
graph-theory
edited Dec 7 '18 at 5:37
Trevor Gunn
14.4k32046
14.4k32046
asked Dec 7 '18 at 4:47
DevAllanPerDevAllanPer
1336
1336
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It does not work with the adjancency matrix nor the degree matrix. To see this, let's look at $K_4$, which we know has $4^{4 - 2}$ spanning trees. (There's nothing special about $K_4$, it's just the first graph I picked.)
$K_4$ has $4$ vertices each of degree $3$. Applying Kirchoff rule to the degree matrix gives $3^3$ spanning trees (incorrect). Applying it to the adjacency matrix gives
$$ left| begin{array}{ccc} 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 0 end{array} right| = 2$$
(also incorrect).
To understand why you need the Laplacian, it is helpful to understand a proof of Kirchoff's theorem. Here is one outline.
Theorem 1. (Binet-Cauchy) If $A$ is $m times n$ and $B$ is $n times m$ then
$$ det(AB) = sum_S det(A[S]) det(B[S]) $$
where the sum is over all $m$-element sets of columns of $A$ and rows of $B$. Here $A[S]$ means we keep only the columns from $S$ and $B[S]$ means we keep only the rows from $S$.
Lemma 2. Let $G$ be a connected graph with no loops (but multiple edges are allowed). Arbitrarily orient $G$ and let $D$ be the signed incidence matrix:
$$ D_{ve} = begin{cases} 1 & v text{ is the head of } e \
-1 & v text{ is the tail of } e \
0 & text{otherwise} end{cases} $$
(Rows are indexed by vertices and columns by edges.) Then $DD^T = L$, the Laplacian of $G$.
Lemma 3. Let $G$ be a connected graph with no loops, oriented arbitrarily. Let $D$ be the signed incidence matrix. If $v in V(G)$ and $S subseteq E(G)$ then $D(v,S)$ denotes the matrix with row $v$ deleted and keeping only the columns belonging to $S$. (So our sets $S$ have $|V(G)| - 1$ elements.)
Then $det D(v,S) = pm 1$ if $(V,S)$ is a spanning tree and $det(v,S) = 0$ if $(V,S)$ is not (i.e. it contains a cycle).
There are of course other proofs of Kirchoff's Theorem. What we can see here is that Lemma 3 is the tool that connects spanning trees to determinants and it is a result about the signed incidence matrix. From Lemma 2 and Binet-Cauchy, we remove the issue with having a sign of $pm 1$ by squaring and we sum over all sets $S$ to count the total number of trees.
Now, if you are given the adjacency matrix, it is easy enough to construct the degrees of each vertex and hence construct the number of spanning trees. On the other hand, if you only have the degrees, you don't know enough about the graph structure to count spanning trees. As an exercise, find two graphs with the same degree sequence but different numbers of spanning trees (remember you can use multiple edges).
$endgroup$
$begingroup$
First of all, thank you for your wonderful explanation! One question though, Are you suggesting that if I were given a large adjacency matrix, I should go ahead and try to map it out and then try to get the Laplacian matrix from that to get the spanning tree #?
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:46
$begingroup$
Just for further reference, and so you can see what I mean, the matrix I was provided is: ibb.co/XXHL529 (i believe the missing # is 1)
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:48
$begingroup$
@DevAllanPer By "map it out" do you mean draw it? That's unnecessary. All you need are the degrees and the adjacency matrix and you can read off the degrees from the adjacency matrix. For example, if vertex 1 is adjacent to vertices 5,7,10 then vertex 1 has degree 3.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 6:05
$begingroup$
Yeah, but in my example (the link i provided) that creates a 8x8 matrix. I don't think our professor would be cruel enough to make us find the determinant of an 8x8 matrix, so whats the trick there?
$endgroup$
– DevAllanPer
Dec 7 '18 at 15:59
$begingroup$
@DevAllanPer Use a computer? I don't know.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 18:30
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3029473%2fmatrix-theorem-kirkhoff-clarification%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It does not work with the adjancency matrix nor the degree matrix. To see this, let's look at $K_4$, which we know has $4^{4 - 2}$ spanning trees. (There's nothing special about $K_4$, it's just the first graph I picked.)
$K_4$ has $4$ vertices each of degree $3$. Applying Kirchoff rule to the degree matrix gives $3^3$ spanning trees (incorrect). Applying it to the adjacency matrix gives
$$ left| begin{array}{ccc} 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 0 end{array} right| = 2$$
(also incorrect).
To understand why you need the Laplacian, it is helpful to understand a proof of Kirchoff's theorem. Here is one outline.
Theorem 1. (Binet-Cauchy) If $A$ is $m times n$ and $B$ is $n times m$ then
$$ det(AB) = sum_S det(A[S]) det(B[S]) $$
where the sum is over all $m$-element sets of columns of $A$ and rows of $B$. Here $A[S]$ means we keep only the columns from $S$ and $B[S]$ means we keep only the rows from $S$.
Lemma 2. Let $G$ be a connected graph with no loops (but multiple edges are allowed). Arbitrarily orient $G$ and let $D$ be the signed incidence matrix:
$$ D_{ve} = begin{cases} 1 & v text{ is the head of } e \
-1 & v text{ is the tail of } e \
0 & text{otherwise} end{cases} $$
(Rows are indexed by vertices and columns by edges.) Then $DD^T = L$, the Laplacian of $G$.
Lemma 3. Let $G$ be a connected graph with no loops, oriented arbitrarily. Let $D$ be the signed incidence matrix. If $v in V(G)$ and $S subseteq E(G)$ then $D(v,S)$ denotes the matrix with row $v$ deleted and keeping only the columns belonging to $S$. (So our sets $S$ have $|V(G)| - 1$ elements.)
Then $det D(v,S) = pm 1$ if $(V,S)$ is a spanning tree and $det(v,S) = 0$ if $(V,S)$ is not (i.e. it contains a cycle).
There are of course other proofs of Kirchoff's Theorem. What we can see here is that Lemma 3 is the tool that connects spanning trees to determinants and it is a result about the signed incidence matrix. From Lemma 2 and Binet-Cauchy, we remove the issue with having a sign of $pm 1$ by squaring and we sum over all sets $S$ to count the total number of trees.
Now, if you are given the adjacency matrix, it is easy enough to construct the degrees of each vertex and hence construct the number of spanning trees. On the other hand, if you only have the degrees, you don't know enough about the graph structure to count spanning trees. As an exercise, find two graphs with the same degree sequence but different numbers of spanning trees (remember you can use multiple edges).
$endgroup$
$begingroup$
First of all, thank you for your wonderful explanation! One question though, Are you suggesting that if I were given a large adjacency matrix, I should go ahead and try to map it out and then try to get the Laplacian matrix from that to get the spanning tree #?
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:46
$begingroup$
Just for further reference, and so you can see what I mean, the matrix I was provided is: ibb.co/XXHL529 (i believe the missing # is 1)
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:48
$begingroup$
@DevAllanPer By "map it out" do you mean draw it? That's unnecessary. All you need are the degrees and the adjacency matrix and you can read off the degrees from the adjacency matrix. For example, if vertex 1 is adjacent to vertices 5,7,10 then vertex 1 has degree 3.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 6:05
$begingroup$
Yeah, but in my example (the link i provided) that creates a 8x8 matrix. I don't think our professor would be cruel enough to make us find the determinant of an 8x8 matrix, so whats the trick there?
$endgroup$
– DevAllanPer
Dec 7 '18 at 15:59
$begingroup$
@DevAllanPer Use a computer? I don't know.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 18:30
|
show 1 more comment
$begingroup$
It does not work with the adjancency matrix nor the degree matrix. To see this, let's look at $K_4$, which we know has $4^{4 - 2}$ spanning trees. (There's nothing special about $K_4$, it's just the first graph I picked.)
$K_4$ has $4$ vertices each of degree $3$. Applying Kirchoff rule to the degree matrix gives $3^3$ spanning trees (incorrect). Applying it to the adjacency matrix gives
$$ left| begin{array}{ccc} 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 0 end{array} right| = 2$$
(also incorrect).
To understand why you need the Laplacian, it is helpful to understand a proof of Kirchoff's theorem. Here is one outline.
Theorem 1. (Binet-Cauchy) If $A$ is $m times n$ and $B$ is $n times m$ then
$$ det(AB) = sum_S det(A[S]) det(B[S]) $$
where the sum is over all $m$-element sets of columns of $A$ and rows of $B$. Here $A[S]$ means we keep only the columns from $S$ and $B[S]$ means we keep only the rows from $S$.
Lemma 2. Let $G$ be a connected graph with no loops (but multiple edges are allowed). Arbitrarily orient $G$ and let $D$ be the signed incidence matrix:
$$ D_{ve} = begin{cases} 1 & v text{ is the head of } e \
-1 & v text{ is the tail of } e \
0 & text{otherwise} end{cases} $$
(Rows are indexed by vertices and columns by edges.) Then $DD^T = L$, the Laplacian of $G$.
Lemma 3. Let $G$ be a connected graph with no loops, oriented arbitrarily. Let $D$ be the signed incidence matrix. If $v in V(G)$ and $S subseteq E(G)$ then $D(v,S)$ denotes the matrix with row $v$ deleted and keeping only the columns belonging to $S$. (So our sets $S$ have $|V(G)| - 1$ elements.)
Then $det D(v,S) = pm 1$ if $(V,S)$ is a spanning tree and $det(v,S) = 0$ if $(V,S)$ is not (i.e. it contains a cycle).
There are of course other proofs of Kirchoff's Theorem. What we can see here is that Lemma 3 is the tool that connects spanning trees to determinants and it is a result about the signed incidence matrix. From Lemma 2 and Binet-Cauchy, we remove the issue with having a sign of $pm 1$ by squaring and we sum over all sets $S$ to count the total number of trees.
Now, if you are given the adjacency matrix, it is easy enough to construct the degrees of each vertex and hence construct the number of spanning trees. On the other hand, if you only have the degrees, you don't know enough about the graph structure to count spanning trees. As an exercise, find two graphs with the same degree sequence but different numbers of spanning trees (remember you can use multiple edges).
$endgroup$
$begingroup$
First of all, thank you for your wonderful explanation! One question though, Are you suggesting that if I were given a large adjacency matrix, I should go ahead and try to map it out and then try to get the Laplacian matrix from that to get the spanning tree #?
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:46
$begingroup$
Just for further reference, and so you can see what I mean, the matrix I was provided is: ibb.co/XXHL529 (i believe the missing # is 1)
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:48
$begingroup$
@DevAllanPer By "map it out" do you mean draw it? That's unnecessary. All you need are the degrees and the adjacency matrix and you can read off the degrees from the adjacency matrix. For example, if vertex 1 is adjacent to vertices 5,7,10 then vertex 1 has degree 3.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 6:05
$begingroup$
Yeah, but in my example (the link i provided) that creates a 8x8 matrix. I don't think our professor would be cruel enough to make us find the determinant of an 8x8 matrix, so whats the trick there?
$endgroup$
– DevAllanPer
Dec 7 '18 at 15:59
$begingroup$
@DevAllanPer Use a computer? I don't know.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 18:30
|
show 1 more comment
$begingroup$
It does not work with the adjancency matrix nor the degree matrix. To see this, let's look at $K_4$, which we know has $4^{4 - 2}$ spanning trees. (There's nothing special about $K_4$, it's just the first graph I picked.)
$K_4$ has $4$ vertices each of degree $3$. Applying Kirchoff rule to the degree matrix gives $3^3$ spanning trees (incorrect). Applying it to the adjacency matrix gives
$$ left| begin{array}{ccc} 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 0 end{array} right| = 2$$
(also incorrect).
To understand why you need the Laplacian, it is helpful to understand a proof of Kirchoff's theorem. Here is one outline.
Theorem 1. (Binet-Cauchy) If $A$ is $m times n$ and $B$ is $n times m$ then
$$ det(AB) = sum_S det(A[S]) det(B[S]) $$
where the sum is over all $m$-element sets of columns of $A$ and rows of $B$. Here $A[S]$ means we keep only the columns from $S$ and $B[S]$ means we keep only the rows from $S$.
Lemma 2. Let $G$ be a connected graph with no loops (but multiple edges are allowed). Arbitrarily orient $G$ and let $D$ be the signed incidence matrix:
$$ D_{ve} = begin{cases} 1 & v text{ is the head of } e \
-1 & v text{ is the tail of } e \
0 & text{otherwise} end{cases} $$
(Rows are indexed by vertices and columns by edges.) Then $DD^T = L$, the Laplacian of $G$.
Lemma 3. Let $G$ be a connected graph with no loops, oriented arbitrarily. Let $D$ be the signed incidence matrix. If $v in V(G)$ and $S subseteq E(G)$ then $D(v,S)$ denotes the matrix with row $v$ deleted and keeping only the columns belonging to $S$. (So our sets $S$ have $|V(G)| - 1$ elements.)
Then $det D(v,S) = pm 1$ if $(V,S)$ is a spanning tree and $det(v,S) = 0$ if $(V,S)$ is not (i.e. it contains a cycle).
There are of course other proofs of Kirchoff's Theorem. What we can see here is that Lemma 3 is the tool that connects spanning trees to determinants and it is a result about the signed incidence matrix. From Lemma 2 and Binet-Cauchy, we remove the issue with having a sign of $pm 1$ by squaring and we sum over all sets $S$ to count the total number of trees.
Now, if you are given the adjacency matrix, it is easy enough to construct the degrees of each vertex and hence construct the number of spanning trees. On the other hand, if you only have the degrees, you don't know enough about the graph structure to count spanning trees. As an exercise, find two graphs with the same degree sequence but different numbers of spanning trees (remember you can use multiple edges).
$endgroup$
It does not work with the adjancency matrix nor the degree matrix. To see this, let's look at $K_4$, which we know has $4^{4 - 2}$ spanning trees. (There's nothing special about $K_4$, it's just the first graph I picked.)
$K_4$ has $4$ vertices each of degree $3$. Applying Kirchoff rule to the degree matrix gives $3^3$ spanning trees (incorrect). Applying it to the adjacency matrix gives
$$ left| begin{array}{ccc} 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 0 end{array} right| = 2$$
(also incorrect).
To understand why you need the Laplacian, it is helpful to understand a proof of Kirchoff's theorem. Here is one outline.
Theorem 1. (Binet-Cauchy) If $A$ is $m times n$ and $B$ is $n times m$ then
$$ det(AB) = sum_S det(A[S]) det(B[S]) $$
where the sum is over all $m$-element sets of columns of $A$ and rows of $B$. Here $A[S]$ means we keep only the columns from $S$ and $B[S]$ means we keep only the rows from $S$.
Lemma 2. Let $G$ be a connected graph with no loops (but multiple edges are allowed). Arbitrarily orient $G$ and let $D$ be the signed incidence matrix:
$$ D_{ve} = begin{cases} 1 & v text{ is the head of } e \
-1 & v text{ is the tail of } e \
0 & text{otherwise} end{cases} $$
(Rows are indexed by vertices and columns by edges.) Then $DD^T = L$, the Laplacian of $G$.
Lemma 3. Let $G$ be a connected graph with no loops, oriented arbitrarily. Let $D$ be the signed incidence matrix. If $v in V(G)$ and $S subseteq E(G)$ then $D(v,S)$ denotes the matrix with row $v$ deleted and keeping only the columns belonging to $S$. (So our sets $S$ have $|V(G)| - 1$ elements.)
Then $det D(v,S) = pm 1$ if $(V,S)$ is a spanning tree and $det(v,S) = 0$ if $(V,S)$ is not (i.e. it contains a cycle).
There are of course other proofs of Kirchoff's Theorem. What we can see here is that Lemma 3 is the tool that connects spanning trees to determinants and it is a result about the signed incidence matrix. From Lemma 2 and Binet-Cauchy, we remove the issue with having a sign of $pm 1$ by squaring and we sum over all sets $S$ to count the total number of trees.
Now, if you are given the adjacency matrix, it is easy enough to construct the degrees of each vertex and hence construct the number of spanning trees. On the other hand, if you only have the degrees, you don't know enough about the graph structure to count spanning trees. As an exercise, find two graphs with the same degree sequence but different numbers of spanning trees (remember you can use multiple edges).
answered Dec 7 '18 at 5:32
Trevor GunnTrevor Gunn
14.4k32046
14.4k32046
$begingroup$
First of all, thank you for your wonderful explanation! One question though, Are you suggesting that if I were given a large adjacency matrix, I should go ahead and try to map it out and then try to get the Laplacian matrix from that to get the spanning tree #?
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:46
$begingroup$
Just for further reference, and so you can see what I mean, the matrix I was provided is: ibb.co/XXHL529 (i believe the missing # is 1)
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:48
$begingroup$
@DevAllanPer By "map it out" do you mean draw it? That's unnecessary. All you need are the degrees and the adjacency matrix and you can read off the degrees from the adjacency matrix. For example, if vertex 1 is adjacent to vertices 5,7,10 then vertex 1 has degree 3.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 6:05
$begingroup$
Yeah, but in my example (the link i provided) that creates a 8x8 matrix. I don't think our professor would be cruel enough to make us find the determinant of an 8x8 matrix, so whats the trick there?
$endgroup$
– DevAllanPer
Dec 7 '18 at 15:59
$begingroup$
@DevAllanPer Use a computer? I don't know.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 18:30
|
show 1 more comment
$begingroup$
First of all, thank you for your wonderful explanation! One question though, Are you suggesting that if I were given a large adjacency matrix, I should go ahead and try to map it out and then try to get the Laplacian matrix from that to get the spanning tree #?
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:46
$begingroup$
Just for further reference, and so you can see what I mean, the matrix I was provided is: ibb.co/XXHL529 (i believe the missing # is 1)
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:48
$begingroup$
@DevAllanPer By "map it out" do you mean draw it? That's unnecessary. All you need are the degrees and the adjacency matrix and you can read off the degrees from the adjacency matrix. For example, if vertex 1 is adjacent to vertices 5,7,10 then vertex 1 has degree 3.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 6:05
$begingroup$
Yeah, but in my example (the link i provided) that creates a 8x8 matrix. I don't think our professor would be cruel enough to make us find the determinant of an 8x8 matrix, so whats the trick there?
$endgroup$
– DevAllanPer
Dec 7 '18 at 15:59
$begingroup$
@DevAllanPer Use a computer? I don't know.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 18:30
$begingroup$
First of all, thank you for your wonderful explanation! One question though, Are you suggesting that if I were given a large adjacency matrix, I should go ahead and try to map it out and then try to get the Laplacian matrix from that to get the spanning tree #?
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:46
$begingroup$
First of all, thank you for your wonderful explanation! One question though, Are you suggesting that if I were given a large adjacency matrix, I should go ahead and try to map it out and then try to get the Laplacian matrix from that to get the spanning tree #?
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:46
$begingroup$
Just for further reference, and so you can see what I mean, the matrix I was provided is: ibb.co/XXHL529 (i believe the missing # is 1)
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:48
$begingroup$
Just for further reference, and so you can see what I mean, the matrix I was provided is: ibb.co/XXHL529 (i believe the missing # is 1)
$endgroup$
– DevAllanPer
Dec 7 '18 at 5:48
$begingroup$
@DevAllanPer By "map it out" do you mean draw it? That's unnecessary. All you need are the degrees and the adjacency matrix and you can read off the degrees from the adjacency matrix. For example, if vertex 1 is adjacent to vertices 5,7,10 then vertex 1 has degree 3.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 6:05
$begingroup$
@DevAllanPer By "map it out" do you mean draw it? That's unnecessary. All you need are the degrees and the adjacency matrix and you can read off the degrees from the adjacency matrix. For example, if vertex 1 is adjacent to vertices 5,7,10 then vertex 1 has degree 3.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 6:05
$begingroup$
Yeah, but in my example (the link i provided) that creates a 8x8 matrix. I don't think our professor would be cruel enough to make us find the determinant of an 8x8 matrix, so whats the trick there?
$endgroup$
– DevAllanPer
Dec 7 '18 at 15:59
$begingroup$
Yeah, but in my example (the link i provided) that creates a 8x8 matrix. I don't think our professor would be cruel enough to make us find the determinant of an 8x8 matrix, so whats the trick there?
$endgroup$
– DevAllanPer
Dec 7 '18 at 15:59
$begingroup$
@DevAllanPer Use a computer? I don't know.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 18:30
$begingroup$
@DevAllanPer Use a computer? I don't know.
$endgroup$
– Trevor Gunn
Dec 7 '18 at 18:30
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3029473%2fmatrix-theorem-kirkhoff-clarification%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown