title: Checking graph properties in linear time given only the adjacency matrix
body: <p>I came across a problem concerning graphs. 
  Let's define a rake graph. </p>
  
  <blockquote>
    <p>A n-vertex graph is a <em>rake</em> when it meets certain conditions:</p>
    
    <ol>
    <li>there is a vertex of degree 1 in the graph</li>
    <li>this vertex is connected to a vertex of degree 2</li>
    <li>this second vertex is connected to another vertex of degree n-2 other vertices may or may not be connected to each other.</li>
    </ol>
  </blockquote>
  
  <p>I have been given an adjacency matrix for a graph of n vertices. My task is to check if the graph represented by the given matrix is a "rake" or not. The catch is that is has to be done in linear time. </p>
  
  <p>I've tried like everything. It's easy to do when you have adjacency list, but how do I make it take  O(n) time with the matrix given?</p>